Acwing 905. 区间选点

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N，表示区间数。
接下来 N行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例：
3 -1 1 2 4 3 5
输出样例：
2

贪心_1.pdf

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         int[][] q = new int[n][2];
  9.         for (int i = 0; i < n; i++) {
  10.             q[i][0] = sc.nextInt();
  11.             q[i][1] = sc.nextInt();
  12.         }
  14.         Arrays.sort(q, (o1, o2) -> o1[1] - o2[1]);
  16.         int cnt = 0, cur = Integer.MIN_VALUE;
  17.         for (int i = 0; i < n; i++) {
  18.             if (q[i][0] > cur) {
  19.                 cnt++;
  20.                 cur = q[i][1];
  21.             }
  22.         }
  23.         System.out.println(cnt);
  24.     }
  25. }

Acwing 908. 最大不相交区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
1≤N≤105
−109≤ai≤bi≤109
输入样例：
3 -1 1 2 4 3 5
输出样例：
2

贪心_2.pdf

  1. //方法一
  2. import java.util.*;
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int[][] q = new int[n][2];
  10.         for (int i = 0; i < n; i++) {
  11.             q[i][0] = sc.nextInt();
  12.             q[i][1] = sc.nextInt();
  13.         }
  15.         Arrays.sort(q, (o1, o2) -> o1[1] - o2[1]);
  17.         int cnt = 0, cur = Integer.MIN_VALUE;
  18.         for (int i = 0; i < n; i++) {
  19.             if (q[i][0] > cur) {
  20.                 cnt++;
  21.                 cur = q[i][1];
  22.             }
  23.         }
  24.         System.out.println(cnt);
  25.     }
  26. }
  1. // 方法二
  2. import java.util.*;
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int[][] p = new int[n][2];
  10.         for (int i = 0; i < n; i++) {
  11.             p[i][0] = sc.nextInt();
  12.             p[i][1] = sc.nextInt();
  13.         }
  15.         int ans = 0;
  16.         Arrays.sort(p, (o1, o2) -> (o1[0] - o2[0]));
  17.         int cur = Integer.MIN_VALUE;
  19.         for (int i = 0; i < n; i++) {
  20.             int a = p[i][0], b = p[i][1];
  21.             if (a > cur) {
  22.                 ans++;
  23.                 cur = b;
  24.             } else 
  25.                 cur = Math.min(cur, b);
  26.         }
  28.         System.out.println(ans);
  29.     }
  30. }

方法3：DP的思路，类似于2008

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.          int n = sc.nextInt();
  7.          int[][] a = new int[n][2];
  8.          for (int i = 0; i < n; i++) {
  9.              a[i][0] = sc.nextInt();
  10.              a[i][1] = sc.nextInt();
  11.          }
  13.          Arrays.sort(a, (o1, o2) -> (o1[1] - o2[1]));
  14.          int[] f = new int[n];
  15.          f[0] = 1;
  16.          for (int i = 1; i < n; i++) {
  17.              int l = 0, r = i;
  18.              while (l < r) {
  19.                  int mid = l + r + 1 >> 1;
  20.                  if (a[mid][1] >= a[i][0])
  21.                     r = mid - 1;
  22.                 else
  23.                     l = mid;
  24.              }
  25.              if (a[l][1] < a[i][0])
  26.                 f[i] = f[l] + 1;
  27.             else
  28.                 f[i] = 1;
  29.             f[i] = Math.max(f[i - 1], f[i]);
  30.          }
  31.          System.out.println(f[n - 1]);
  32.     }
  33. }

Acwing 906. 区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1≤N≤105
−109≤ai≤bi≤109
输入样例：
3 -1 1 2 4 3 5
输出样例：
2

贪心_3.pdf

随便挑一个放的原因是，如果能放到其它组中，说明后面遍历的区间也能放到其他组中，效果等价

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         int[][] a = new int[n][2];
  10.         for (int i = 0; i < n; i++) {
  11.             a[i][0] = sc.nextInt();
  12.             a[i][1] = sc.nextInt();
  13.         }
  15.         Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);
  16.         PriorityQueue<Integer> q = new PriorityQueue<>();
  18.         for (int i = 0; i < n; i++) {
  19.             if (q.isEmpty() || q.peek() >= a[i][0])
  20.                 q.offer(a[i][1]);
  21.             else {
  22.                 q.poll();
  23.                 q.offer(a[i][1]);
  24.             }
  25.         }
  26.         System.out.println(q.size());
  27.     }
  28. }

方法2：
利用差分的思想，每添加一个区间，就将这个区间内所有数加1
前缀和就是当前区间的最少分组数

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         Map<Integer, Integer> map = new TreeMap<>();
  8.         for (int i = 0; i < n; i++) {
  9.             int a = sc.nextInt(), b = sc.nextInt();
  10.             map.merge(a, 1, Integer::sum);
  11.             map.merge(b + 1, -1, Integer::sum);
  12.         }
  13.         int max = 0, cnt = 0;
  14.         for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
  15.             cnt += pair.getValue();
  16.             if (max < cnt)
  17.                 max = cnt;
  18.         }
  19.         System.out.println(max);
  20.     }
  21. }

Acwing 907. 区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
输入格式
第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。
第二行包含整数 N，表示给定区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出 −1。
数据范围
1≤N≤105,
−109≤ai≤bi≤109,
−109≤s≤t≤109
输入样例：
1 5 3 -1 3 2 4 3 5
输出样例：
2

贪心_4.pdf

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int st = sc.nextInt(), ed = sc.nextInt();
  7.         int n = sc.nextInt();
  9.         int[][] a = new int[n][2];
  10.         for (int i = 0; i < n; i++) {
  11.             a[i][0] = sc.nextInt();
  12.             a[i][1] = sc.nextInt();
  13.         }
  15.         Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);
  17.         int cnt = 0, cur = st;
  18.         for (int i = 0; i < n; i++) {
  19.             int j = i;
  20.             int last = cur;
  21.             while (j < n && a[j][0] <= cur) {
  22.                 last = Math.max(last, a[j][1]);
  23.                 j++;
  24.             }
  25.             if (last == cur)
  26.                 break;
  27.             cnt++;
  28.             cur = last;
  29.             i = j - 1;
  30.             if (cur >= ed)
  31.                 break;
  32.         }
  33.         if (cur >= ed) System.out.println(cnt);
  34.         else System.out.println(-1);
  35.     }
  36. }