Skip to content

Offline Algorithm

Table of Contents

2343. Query Kth Smallest Trimmed Number

  • LeetCode | 力扣

  • 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

  • LeetCode | 力扣

  • 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

  • LeetCode | 力扣

  • 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

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Sorting, Monotonic Stack

3382. Maximum Area Rectangle With Point Constraints II

Comments