网站论文参考文献网站制作软件
区间合并：区间合并问题
区间合并
www.acwing.com/problem/content/805/
-
按区间的左端点排序
-
扫描整个区间，在这过程中把可能有交点的区间合并
- 全包含：不做改动
- 相交：right 后移
- 相离：更新至下一个维护区间
import java.util.*;public class Main {static final int N = 100010;static Pair[] pairs = new Pair[N];static class Pair implements Comparable<Pair> {int l, r;public Pair(int l, int r) {this.l = l;this.r = r;}@Overridepublic int compareTo(Pair o) {if (this.l == o.l) {return this.r - o.r;}return this.l - o.l;}} public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 0; i < n; i++) {int l = sc.nextInt();int r = sc.nextInt();pairs[i] = new Pair(l, r);}Arrays.sort(pairs, 0, n);int result = 1;int right = pairs[0].r;for (int i = 1; i < n; i++) {if (pairs[i].l <= right) {// 合并区间right = Math.max(right, pairs[i].r);} else {// 新区间result++;right = pairs[i].r;}}System.out.println(result);}
}