Offline Algorithm¶
Table of Contents¶
- 2343. Query Kth Smallest Trimmed Number (Medium)
- 2070. Most Beautiful Item for Each Query (Medium)
- 1847. Closest Room (Hard)
- 2503. Maximum Number of Points From Grid Queries (Hard)
- 1851. Minimum Interval to Include Each Query (Hard)
- 1697. Checking Existence of Edge Length Limited Paths (Hard)
- 2940. Find Building Where Alice and Bob Can Meet (Hard)
- 2747. Count Zero Request Servers (Medium)
- 1938. Maximum Genetic Difference Query (Hard)
- 2736. Maximum Sum Queries (Hard)
- 3382. Maximum Area Rectangle With Point Constraints II (Hard)
2343. Query Kth Smallest Trimmed Number¶
-
Tags: Array, String, Divide And Conquer, Sorting, Heap Priority Queue, Radix Sort, Quickselect
2070. Most Beautiful Item for Each Query¶
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
std::sort(items.begin(), items.end(),
[](const auto& a, const auto& b) { return a[0] < b[0]; });
vector<int> idx(queries.size());
iota(idx.begin(), idx.end(), 0);
std::sort(idx.begin(), idx.end(),
[&](int i, int j) { return queries[i] < queries[j]; });
vector<int> res(queries.size());
int max_beauty = 0;
size_t j = 0;
for (int i : idx) {
int q = queries[i];
while (j < items.size() && items[j][0] <= q) {
max_beauty = max(max_beauty, items[j][1]);
j++;
}
res[i] = max_beauty;
}
return res;
}
int main() {
vector<vector<int>> items = {{1, 2}, {2, 4}, {3, 2}, {5, 6}, {3, 5}};
vector<int> queries = {1, 2, 3, 4, 5, 6};
vector<int> res = maximumBeauty(items, queries);
assert((res == vector<int>{2, 4, 5, 5, 6, 6}));
return 0;
}
1847. Closest Room¶
2503. Maximum Number of Points From Grid Queries¶
-
Tags: Array, Two Pointers, Breadth First Search, Union Find, Sorting, Heap Priority Queue, Matrix
1851. Minimum Interval to Include Each Query¶
1697. Checking Existence of Edge Length Limited Paths¶
2940. Find Building Where Alice and Bob Can Meet¶
-
Tags: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Heap Priority Queue, Monotonic Stack
2747. Count Zero Request Servers¶
1938. Maximum Genetic Difference Query¶
2736. Maximum Sum Queries¶
-
Tags: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Sorting, Monotonic Stack