核心思路:
(1)每次找到包括st的区间,用其中最大值更新st,直到超过ed 或最大值小于st(无解)就结束。
(2)每次找区间,不需要都遍历所有区间,用前面大于st的第一个区间 j~n 去找最大值;
因为上次的最大值r更新成了st,在0-j-1个区间里只有有最大值r的那个区间能包括r,其他 0 ~ j-1 里都没有,而这个区间用二次没有意义,所以从j~n里面找包括更新后st的区间,重复操作知道超过ed或 无解情况:(最大值小于st,没有区间更新st,不能覆盖 (st,st+1)之间的数 )
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int st=sc.nextInt();
int ed=sc.nextInt();
int n=sc.nextInt();
int[][] a=new int[n][2];
for(int i=0;i<n;i++){
a[i][0]=sc.nextInt();
a[i][1]=sc.nextInt();
}
Arrays.sort(a,(o1,o2)->{
return o1[0]-o2[0];
});
int res=0;
boolean flag=false;
for(int i=0;i<n;i++){
int j=i;
int r=Integer.MIN_VALUE;//初始化负无穷
while(j<n&&a[j][0]<=st){ //遍历所有能包括到st的点, st是上一个r也是包括上一个st的最大值
//所以包括上一个st的区间最右点是其他区间不能包括到的,
//也就是说能取到上一个st的区间取不到现在的st = r,从取不到上一个st的区间里找,
//st变大,所以找的左端点也肯定更大,上一个离st最近的左端点刚好是j,j要么是出界要么是大于st
//所以从第j个开始找能取到现在st的区间
r=Math.max(r,a[j][1]); //最大右端点
j++;//下一个区间
}
res++;//选定了一个区间
if(r<=st){//看这个区间右端点是不是小于st,则没有更大的值走下一步了
//r=st也无效,说明包括st并且右端点也是st,下一次找也还是更新r=st,st=r直到循环结束
flag=false;
break;
}
if(r>=ed){ //超过ed就完成了覆盖
flag=true;
break;
}
st=r; //更新st和i
i=j-1;
}
System.out.println(flag?res:-1);
}
}
2021-02-20
二刷苦逼复习:
重新写一遍写成了不一样的结果
import java.util.*;
public class Main{
static int N = 100010;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
int t = sc.nextInt();
int n = sc.nextInt();
Pair p[] = new Pair[n];
for(int i = 0; i < n; i ++){
int l = sc.nextInt();
int r = sc.nextInt();
p[i] = new Pair(l, r);
}
Arrays.sort(p, 0, n);
int ed = Integer.MIN_VALUE; // 包含s点且能取到的最远右端点
int res = 1; // 最后的一个区间,因为ed >= t直接break了
for(int i = 0; i < n; i ++){ // 左端点排序遍历
if(ed >= t) break; // 右端点已经取到了边界t
if(p[i].l <= s) ed = Math.max(ed, p[i].r); // 找左端点小于起点的最远右端点
else{ // 后续的左端点都会大于s,所以更新s
res ++; // 此时最大右端点取到了ed, 新增这个区间
s = ed;
if(p[i].l <= s) ed = Math.max(ed, p[i].r);
// 当前区间因为左端点<=s被跳过,所以跳到下一层循环后这个区间没被计算过:也可以写成 i = i-1
}
}
System.out.println(ed >= t ? res : -1);
}
static class Pair implements Comparable<Pair>{
int l, r;
Pair(int l, int r){
this.l = l;
this.r = r;
}
public int compareTo(Pair o){
return this.l - o.l;
}
}
}