题目描述
blablabla
样例
blablabla
算法1
blablabla
时间复杂度分析:blablabla
C++ 代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main{
static class Interval implements Comparable<Interval>{
int x;
int y;
public Interval(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Interval o) {
return this.x>o.x?1:-1;
}
@Override
public String toString() {
return "Interval{" +
"x=" + x +
", y=" + y +
'}';
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
ArrayList<Interval> segs=new ArrayList<>();
for (int i = 0; i <n ; i++) {
segs.add(new Interval(scanner.nextInt(),scanner.nextInt()));
}
ArrayList<Interval> res=merge(segs);
System.out.println(res.size());
}
private static ArrayList<Interval> merge(ArrayList<Interval> segs) {
Collections.sort(segs);
ArrayList<Interval> res=new ArrayList<>();
int st=Integer.MIN_VALUE;
int ed=Integer.MIN_VALUE;
for (int i = 0; i <segs.size() ; i++) {
if (ed<segs.get(i).x){
if (st!=Integer.MIN_VALUE)
res.add(new Interval(st,ed));
st=segs.get(i).x;
ed=segs.get(i).y;
}else
ed=Math.max(ed,segs.get(i).y);
}
if (st!=Integer.MIN_VALUE)
res.add(new Interval(st,ed));
return res;
}
}