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

一、题目描述

给定 ( N ) 个闭区间 ([a_i, b_i])，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。输出可选取区间的最大数量。

输入格式

第一行包含整数 ( N )，表示区间数。
接下来 ( N ) 行，每行包含两个整数 ( a_i, b_i )，表示一个区间的两个端点。

输出格式

输出一个整数，表示可选取区间的最大数量。

数据范围

( 1 \leq N \leq 10^5 )，( -10^9 \leq a_i \leq b_i \leq 10^9 )

输入样例

3
-1 1
2 4
3 5

输出样例

2

二、解题思路

核心发现：与「区间选点」同源

这道题的解法和 AcWing 905. 区间选点 完全一致。两道题本质都是通过贪心策略最大化区间利用率，只是问题描述角度不同：

• 区间选点：求最少点数覆盖所有区间；
• 最大不相交区间：求最多不重叠区间数量。
  两者的最优解思路完全互通，核心都是「按右端点排序 + 贪心选择」。

贪心策略

1. 按右端点排序：将所有区间按右端点从小到大排序。这样做的目的是，每次选择区间时，尽可能保留数轴上的剩余空间，以容纳更多后续区间。
2. 筛选不相交区间：
   • 初始化最后选中区间的结束边界 ed 为极小值（如负无穷），结果计数 res 为 0。
   • 遍历排序后的区间：
     • 若当前区间的左端点 > ed，说明该区间与之前选中的区间不相交，选择该区间，res 加 1，同时更新 ed 为当前区间的右端点。
     • 若当前区间与之前选中的区间重叠（包括端点），则跳过该区间，避免冲突。

为什么这样有效？

按右端点排序后，每次选中的区间都是当前能找到的「最早结束」的区间。这种选择能最大限度地留出后续空间，让更多区间有机会被选中，从而达到「最大不相交数量」的目标。

例如样例中排序后区间为 ([-1,1])、([2,4])、([3,5])：

• 选中 ([-1,1])，ed=1；
• 下一个区间 ([2,4]) 的左端点 2 > 1，选中，res=2，ed=4；
• 最后一个区间 ([3,5]) 与 ([2,4]) 重叠，跳过；
• 最终结果为 2，与样例输出一致。

三、Java 代码实现

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] intervals = new int[n][2];
        
        for (int i = 0; i < n; i++) {
            intervals[i][0] = sc.nextInt(); // 区间左端点
            intervals[i][1] = sc.nextInt(); // 区间右端点
        }
        sc.close();
        
        // 按区间右端点从小到大排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        
        int res = 0;
        int ed = Integer.MIN_VALUE; // 初始结束边界设为极小值
        
        for (int[] interval : intervals) {
            int l = interval[0];
            int r = interval[1];
            // 若当前区间左端点 > 上一个选中区间的右端点，说明不相交
            if (l > ed) {
                res++;
                ed = r; // 更新结束边界为当前区间右端点
            }
        }
        
        System.out.println(res);
    }
}

代码说明

1. 输入处理：使用二维数组存储区间，通过 Scanner 读取输入数据。
2. 排序逻辑：利用 Arrays.sort 结合自定义比较器，按区间右端点升序排序。
3. 贪心筛选：遍历排序后的区间，筛选出不相交的区间并计数，最终输出结果。
4. 时间复杂度：( O(n \log n) )，核心开销在排序（( n ) 为区间数量），遍历过程仅需 ( O(n) )。
5. 空间复杂度：( O(\log n) )，排序所需的递归栈空间（Java 内置排序为双轴快排）。

四、注意事项

1. 边界处理：初始 ed 设为 Integer.MIN_VALUE，确保第一个区间一定能被选中。
2. 排序稳定性：按右端点排序时，若两个区间右端点相同，左端点顺序不影响结果，无需额外处理。
3. 数据规模适配：代码采用二维数组存储，避免自定义类的额外开销，适配 ( 10^5 ) 级别的数据规模。

五、总结

这道题的核心是发现其与「区间选点」的同源性，掌握「按右端点排序 + 贪心选择」的模板后，可快速解决。贪心算法的关键在于找到「局部最优解」并推导出「全局最优解」，本题中「选择最早结束的区间」就是局部最优，最终实现全局最大不相交数量。

这类区间贪心问题的通用思路可总结为：

1. 排序（按左端点或右端点，根据问题场景选择）；
2. 遍历筛选（按贪心策略选择区间或点）。

掌握该模板后，可轻松应对「区间覆盖」「区间选点」「最大不相交区间」等同类问题。

LeetCode 435. 无重叠区间

一、题目描述

给定一个区间集合 intervals，其中 intervals[i] = [start_i, end_i]，返回需要移除区间的最小数量，使剩余区间互不重叠。注意：仅在端点接触的区间不算重叠（如 [1,2] 和 [2,3] 不重叠）。

示例

• 示例 1：
  输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
  输出：1
  解释：移除 [1,3] 后，剩余区间无重叠。
• 示例 2：
  输入：intervals = [[1,2],[1,2],[1,2]]
  输出：2
  解释：需移除两个 [1,2]，仅剩一个区间无重叠。
• 示例 3：
  输入：intervals = [[1,2],[2,3]]
  输出：0
  解释：区间已无重叠，无需移除。

提示

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= start_i < end_i <= 5 * 10^4

二、解题思路

核心转化：最小移除数 = 总区间数 - 最大不相交区间数

这道题的本质的是求「最大不相交区间数量」—— 因为要移除的区间最少，就意味着要保留的不相交区间最多。两者关系为：
需要移除的区间数 = 总区间数 - 最大不相交区间数

贪心策略（与「最大不相交区间」一致）

1. 按右端点排序：将所有区间按右端点升序排序。这样做能让每次选择的区间尽可能早地结束，留出更多空间容纳后续区间，从而最大化不相交区间的数量。
2. 筛选不相交区间：
   • 初始化最后保留区间的结束边界 lastEnd 为极小值，最大不相交区间数 maxNonOverlap 为 0。
   • 遍历排序后的区间：
     • 若当前区间的左端点 >= lastEnd（无重叠），则保留该区间，maxNonOverlap 加 1，更新 lastEnd 为当前区间的右端点。
     • 若重叠，则跳过该区间（后续需移除）。

逻辑验证（以示例 1 为例）

示例 1 输入：[[1,2],[2,3],[3,4],[1,3]]
排序后区间：[[1,2],[1,3],[2,3],[3,4]]

• 保留 [1,2]，lastEnd=2，maxNonOverlap=1；
• 区间 [1,3] 与 [1,2] 重叠，跳过；
• 区间 [2,3] 的左端点 2 >= 2，保留，lastEnd=3，maxNonOverlap=2；
• 区间 [3,4] 的左端点 3 >= 3，保留，maxNonOverlap=3；
  总区间数 4 - 最大不相交数 3 = 1，与示例输出一致。

三、Java 代码实现

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        // 按区间右端点升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });

        int n = intervals.length;
        int maxNonOverlap = 1; // 至少有一个不相交区间
        int lastEnd = intervals[0][1]; // 第一个区间的右端点

        for (int i = 1; i < n; i++) {
            int currentStart = intervals[i][0];
            // 无重叠时保留当前区间
            if (currentStart >= lastEnd) {
                maxNonOverlap++;
                lastEnd = intervals[i][1];
            }
        }

        // 最小移除数 = 总区间数 - 最大不相交区间数
        return n - maxNonOverlap;
    }

    // 测试代码
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] intervals1 = {{1,2},{2,3},{3,4},{1,3}};
        System.out.println(solution.eraseOverlapIntervals(intervals1)); // 输出 1
        int[][] intervals2 = {{1,2},{1,2},{1,2}};
        System.out.println(solution.eraseOverlapIntervals(intervals2)); // 输出 2
        int[][] intervals3 = {{1,2},{2,3}};
        System.out.println(solution.eraseOverlapIntervals(intervals3)); // 输出 0
    }
}

代码说明

1. 排序优化：按右端点排序是核心，确保每次保留的区间最早结束，最大化后续容纳空间。
2. 边界处理：空输入直接返回 0，避免异常。
3. 时间复杂度：O(n log n)，排序占主要开销，遍历仅 O(n)，适配 10^5 级数据。
4. 空间复杂度：O(log n)，排序所需递归栈空间（Java 内置排序为双轴快排）。

四、注意事项

1. 区间端点判定：题目明确「仅端点接触不算重叠」，因此判断条件为 currentStart >= lastEnd（而非 >）。
2. 排序避免溢出：本题区间端点范围较小（-5e4 ~ 5e4），用 a[1]-b[1] 比较可行；若端点范围更大（如 2^31-1），需改用 Integer.compare(a[1], b[1]) 避免溢出。
3. 与同类题关联：本题与「最大不相交区间数量」「用最少箭引爆气球」思路完全同源，均为「按右端点排序 + 贪心筛选」，可统一记忆模板。

五、总结

这道题的关键是将「最小移除区间数」转化为「最大不相交区间数」，再用成熟的贪心模板求解。贪心算法的核心是找到「局部最优解」（每次选最早结束的区间），最终推导「全局最优解」（最多不相交区间）。

掌握这类区间贪心问题的通用模板：

1. 排序（按右端点或左端点，优先右端点最大化后续空间）；
2. 遍历筛选（按重叠条件保留区间，统计最优解）；
3. 转化问题（如本题将「移除数」转化为「保留数」的差值）。