AcWing:5459. 区间嵌套

给定?n?个正整数区间，编号?1～n。

其中，第?i?个区间为?[li,ri]。

请你找到一对不同的整数?j,k（1≤j,k≤n），使得区间?j?完全包含于区间?k。

如果?lj≥lk 且?rj≤rk，则区间?j?完全包含于区间?k。

输入格式

第一行包含整数?n。

接下来?n?行，其中第?i?行包含两个整数?li,ri。

输出格式

如果题目无解，则输出一行?-1 -1。

否则，在一行内输出一对不同的整数?j,k，满足区间?j?完全包含于区间?k。

如果答案不唯一，则输出任意合理答案均可。

数据范围

前?6?个测试点满足?1≤n≤5。
所有测试点满足?1≤n≤3×10^5，1≤li≤ri≤10^9。

输入样例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

?一道经典的区间覆盖问题

可以将两边分别升序和倒序,观察是否包含

?以下是AC代码

#include <bits/stdc++.h>

/* 定义 */
using namespace std;
typedef long long LL;
typedef pair<int , int> PII;

/* 定义变量 */
const int N = 3e5 + 10;
pair<int , PII>ans[N];
int n;

/* 快排规则 */
bool cmp(pair<int , PII> a, pair<int , PII> b)
{
    if(a.first == b.first) return a.second.first > b.second.first;
    else return a.first < b.first;
}

int main()
{ 
    /* 正常读入 */
    cin >> n;
    for(int i = 0;i < n; i ++)
    {
        cin >> ans[i].first >> ans[i].second.first;
        ans[i].second.second = i + 1; // 记录编号
    }

    /* 快排 */
    sort(ans, ans + n , cmp);

    /* 初始化 */
    int i = 0;
    bool f = false;
    for(i = 0;i < n - 1;i ++)
    {
        if(ans[i].second.first >= ans[i + 1].second.first) // 已经快排好了,直接前后比较
        {
            f = true;
            break;
        }
            
    }

    /* 判断输出 */
    if(f)
    cout << ans[i + 1].second.second << " " << ans[i].second.second; 
    else cout << "-1 -1";

    /* 检查 */
    /*cout << endl;
    for(int i = 0 ;i < n; i ++)
    {
        cout << ans[i].first <<" "<< ans[i].second.first <<" "<< ans[i].second.second << endl;
    }*/
    
    return 0; // 好习惯
}