数轴上定长区间与给定区间同时相交的最大数量

模型

在[1, n]中给定k个长度不等区间[l, r]，求[1, n]中长度为d的区间与给定区间同时相交的最大数量

代码

int solve(int n, int d, int k, std::vector<PII> &a) {
    std::sort(a.begin(), a.end());
    std::priority_queue<int, std::vector<int>, std::greater<int>> f;
    int max = 0, idx = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        while (idx < k && a[idx].first == i) {
            f.push(a[idx].second);
            idx++;
        }
        while (i - j + 1 > d) {
            j++;
        }
        while (f.size() && f.top() < j) {
            f.pop();
        }
        max = std::max(max, (int)f.size());
    }
    return max;
}