AcWing 803. 区间合并---java
原题链接
简单
作者:
土豆有点
,
2020-04-15 13:13:56
,
所有人可见
,
阅读 628
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Pairs> add = new ArrayList<>();
for(int i = 0; i < n; i++){
int l = sc.nextInt();
int r = sc.nextInt();
add.add(new Pairs(l,r));
}
//按照左区间排序
add = add.stream().sorted(Comparator.comparing(Pairs::getFirst)).collect(java.util.stream.Collectors.toList());
int count = 1;
int l = add.get(0).getFirst();
int r = add.get(0).getSecond();
for(int i = 1; i < add.size(); i++){
if(r >= add.get(i).getFirst() && r<= add.get(i).getSecond()){
r = add.get(i).getSecond();
}
if(r < add.get(i).getFirst()){
l = add.get(i).getFirst();
r = add.get(i).getSecond();
count++;
}
}
System.out.print(count);
}
}
class Pairs{
int first;
int second;
public Pairs(int first, int second) {
this.first = first;
this.second = second;
}
public int getFirst() {
return first;
}
public int getSecond() {
return second;
}
}