AcWing 803. 区间合并 原题链接
给定 nn 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤1000001≤n≤100000, −109≤li≤ri≤109−109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
private static class Interval implements Comparable<Interval>{
int left;
int right;
public Interval(int left, int right) {
this.left = left;
this.right = right;
}
@Override
public int compareTo(Interval o) {
return this.left - o.left;
}
}
public static void main(String[] args) {
int n = in.nextInt();
List<Interval> list = new ArrayList<>();
while (n-- > 0) {
list.add(new Interval(in.nextInt(), in.nextInt()));
}
Collections.sort(list);
int right = list.get(0).right;
int res = 1;
for (int i = 1; i < list.size(); i++) {
if (list.get(i).left <= right) {
right = Math.max(right, list.get(i).right);
}else {
res++;
right = list.get(i).right;
}
}
out.println(res);
out.flush();
out.close();
}