區間合并：區間合并問題

區間合并

www.acwing.com/problem/content/805/

1. 按區間的左端點排序

2. 掃描整個區間，在這過程中把可能有交點的區間合并

   1. 全包含：不做改動
   2. 相交：right 后移
   3. 相離：更新至下一個維護區間

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);}
}