アルゴリズム設計と分析1.4区間

1137 ワード

★タイトルの説明
N区間あり、i区間目の端点がliとri、すなわちi区間目が[li,ri]を覆っている
最小番号の区間がすべての区間を含むかどうか.存在する場合は区間番号を出力、そうでない場合は「-1」を出力.
区間含むとは、一方の区間[a,b]が他方の区間[c,d]を含むと仮定する、a<=c<=d<=bを満たす必要がある.
★入力形式
1行目の整数Nは区間個数を表し、N<=10000000
次のN行は1行あたり2個の整数li、riはi番目の区間の端点を表し、1<=li<=ri<=1億円
30%のデータに対して、N<=100、1<=li<=ri<=100
80%のデータに対して、N<=1000、1<=li<=ri<=1000
100%のデータに対して、N<=1000000、1<=li<=ri<=1000000
★出力フォーマット
1つの整数は、要求区間を満たす番号を表します.存在しない場合は-1を出力します.
★サンプル入力
3
1 1
2 2
3 3

★サンプル出力
-1
/*
    :
                
             
*/

#include
using namespace std;

int main(){
    int n;
    cin>>n;
    
    int l,r,minL,maxR;
    scanf("%d%d",&minL,&maxR);
    int resL=minL,resR=maxR, resid=1; //       ,            
    for(int i=2; i<=n; ++i){
        scanf("%d%d",&l,&r);
        minL = min(l,minL);
        maxR = max(r,maxR);
        
        if(resR-resL