AcWing 803. 区间合并
原题链接
简单
作者:
Phil.
,
2023-12-13 21:12:44
,
所有人可见
,
阅读 40
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static int N = 100010;
public static int n ;
public static ArrayList<Pair> segs= new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0 ; i < n ; i ++){
int l = sc.nextInt();
int r = sc.nextInt();
segs.add(new Pair(l,r));
}
Collections.sort(segs);
ArrayList<Pair> res = new ArrayList<>();
int st = (int)-2e9;
int ed = (int)-2e9;
for (Pair seg : segs){
// 1. 线段不相交
if(ed < seg.x){
if(st != (int)-2e9){
res.add(new Pair(st,ed));
}
st = seg.x;
ed = seg.y;
}
// 2. 线段相交
else{
ed=Math.max(ed,seg.y);
}
}
if(ed != (int)-2e9){
res.add(new Pair(st,ed));
}
System.out.println(res.size());
}
}
class Pair implements Comparable<Pair>{
int x;
int y;
public Pair(int x,int y ){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pair o) {
return Integer.compare(x,o.x);
}
}