AcWing 803. 区间合并(Java解法^ ^)
原题链接
简单
作者:
是晴天呀
,
2021-04-16 10:23:04
,
所有人可见
,
阅读 492
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int n;
static Section sec[];
static int ans=1; //已经取了排序后第一个区间的右端点
static class Section implements Comparable<Section>{
int l;
int r;
public Section(int l,int r) {
this.l=l;
this.r=r;
}
public int compareTo(Section o) {
return this.l-o.l; //按照左端点排序
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
n=Integer.parseInt(br.readLine());
sec=new Section[n];
for(int i=0;i<n;i++) {
String srr[]=br.readLine().split(" ");
int ll=Integer.parseInt(srr[0]);
int rr=Integer.parseInt(srr[1]);
sec[i]=new Section(ll,rr);
}
Arrays.sort(sec);
int ed=sec[0].r;
//本题要维护一个最终的端点ed
//首先取ed为排序后第一个区间的右端点,然后一个一个针对后面的区间
//如果要针对的区间的左端点严格大于当前ed,则直接更新,没的说
//如果要针对的区间的左端点并没有大于ed, 则考虑一下是否延长当前的ed!
for(int i=1;i<sec.length;i++) {
if(sec[i].l>ed) {
ans++;
ed=sec[i].r;
}else {
ed=Math.max(ed, sec[i].r);
}
}
System.out.println(ans);
}
}