アルゴリズム設計と分析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を出力します.
★サンプル入力
★サンプル出力
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