AcWing 907. 区间覆盖(java双指针)
原题链接
简单
作者:
JC_91
,
2021-06-02 19:50:51
,
所有人可见
,
阅读 254
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int l = sc.nextInt();
int r = sc.nextInt();
int n = sc.nextInt();
List<int[]> list = new ArrayList();
while(n-->0){
int[] arr = new int[2];
arr[0] = sc.nextInt();
arr[1] = sc.nextInt();
list.add(arr);
}
Collections.sort(list, new Comparator<int[]>(){
public int compare(int[] o1,int[] o2){
return o1[0]-o2[0];
}
});
int idx = 0;
int ans = 0;
while(l<r){
int t = -1;
int max = l;
while(idx<list.size()){
int[] arr = list.get(idx);
if(arr[0]<=l && arr[1]>=l){
if(arr[1]>max){
t = idx;
max = arr[1];
}
}else if(arr[0]>l){
break;
}
idx++;
}
if(t == -1){
System.out.println(-1);
return;
}
ans++;
l = list.get(t)[1];
}
System.out.println(ans);
}
}