题目描述

难度分:$1500$

输入$n(1 \leq n \leq 3 \times 10^5)$和$n$个闭区间，区间的左右端点在$[1,10^9]$内。

从这$n$个区间中，选出两个区间$[L[i], R[i]]$和$[L[j], R[j]]$， 满足$i \neq j$且$L[j] \leq L[i] \leq R[i] \leq R[j]$，也就是区间$j$包含区间$i$。

输出$i$和$j$（按照输入的顺序，下标从$1$开始）。如果不存在这样的区间，输出两个$-1$。

输入样例$1$

5
1 10
2 9
3 9
2 3
2 9

输出样例$1$

2 1

输入样例$2$

3
1 5
2 6
6 20

输出样例$2$

-1 -1

算法

贪心

思路比较直观，但实现起来有些细节。先将所有区间按照右端点排序，然后遍历有序的区间数组$intervals$，每个区间的信息是个三元组（左端点，右端点，区间编号）。当遍历到区间$intervals[i]=(left_i, right_i, i)$时，将所有右端点为$right_i$的区间的左端点+编号组成二元组（左端点，区间编号）加入到一个有序$set$中。这样一来，所有右端点不超过$right_i$的区间左端点就都被加入到$set$中了，然后我们在$set$中二分查找，找到第一个区间左端点大于等于$left_i$的位置，然后就分为两种情况：

1. 如果当前位置的区间编号$j$和$i$不同，那答案就是$i$和$j$两个区间，区间$i$是完全包含区间$j$的。
2. 否则如果有下一个位置，那答案就是$i$和下一个位置的区间索引。

如果遍历完所有的区间还没找到答案，就输出两个$-1$。在这个过程中，我们需要存一个映射$r2l$“右端点$\rightarrow$（左端点，区间编号）”，这样就能在遍历到区间$(left_i,right_i,i)$时，将所有右端点为$right_i$的区间左端点和编号遍历一遍加入平衡树。而下一次再遍历到$right_i$这个右端点时，为了不重复遍历这个右端点的左端点+区间编号，添加一个标记数组$vis$，遍历完了$right_i$就$vis[right_i]=$true进行标记。

这里$r2l$和$vis$可以直接用哈希表，我懒得重写哈希函数所以用了数组，而使用数组需要考虑到区间$L[i]$和$R[i]$的值域范围，本题的范围可以达到$10^9$，要对其进行离散化。

复杂度分析

时间复杂度

排序和离散化的时间复杂度均为$O(nlog_2n)$。接下来需要按右端点升序的顺序遍历每个区间$intervals[i]=(left_i,right_i,i)$，每个区间有对平衡树插入和二分查找的操作，时间复杂度为$O(log_2n)$，而每个区间的“左端点+区间编号”信息只会进入平衡树一次，所以总体的时间复杂度为$O(nlog_2n)$。

空间复杂度

预处理中，离散化需要用哈希表存每个数值的离散化索引，最差情况下需要存$O(n)$级别的键值对。在遍历每个区间计算答案的时候，平衡树最多也是存$O(n)$级别的二元组，$vis$数组需要标记$O(n)$级别的位置，二维数组$r2l$中的元素数量也是$O(n)$级别。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> pos;
    vector<array<int, 3>> intervals;
    for(int i = 1; i <= n; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        pos.push_back(l);
        pos.push_back(r);
        intervals.push_back({l, r, i});
    }
    sort(intervals.begin(), intervals.end(), [&](auto& a, auto& b) {
        return a[1] != b[1]? a[1] < b[1]: a[0] > b[0];
    });
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    map<int, int> val2pos;
    int sz = pos.size();
    for(int i = 0; i < sz; i++) {
        val2pos[pos[i]] = i + 1;
    }
    vector<vector<array<int, 2>>> r2l;
    r2l.resize(sz + 1);
    for(auto& interval: intervals) {
        int left = interval[0], right = interval[1], index = interval[2];
        int r = val2pos[right];
        r2l[r].push_back({left, index});
    }
    vector<int> vis(sz + 1);
    set<pair<int, int>> bt;
    bool ok = false;
    for(int i = 0; i < n; i++) {
        int left = intervals[i][0], right = intervals[i][1], index = intervals[i][2];
        int r = val2pos[right];
        if(vis[r] == 0) {
            for(auto&pir: r2l[r]) {
                int left = pir[0], index = pir[1];
                bt.insert({left, index});
            }
            vis[r] = 1;
        }
        auto it = bt.lower_bound({left, 0});
        if(it != bt.end()) {
            if(it->second != index) {
                printf("%d %d\n", it->second, index);
                ok = true;
                break;
            }else {
                if(next(it) != bt.end()) {
                    printf("%d %d\n", next(it)->second, index);
                    ok = true;
                    break;
                }
            }
        }
    }
    if(!ok) puts("-1 -1");
    return 0;
}