排序应用：合并区间与会议室问题

合并区间（LeetCode 56）

先按起点排序，再逐一合并。

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> res = new ArrayList<>();
    for (int[] cur : intervals) {
        if (res.isEmpty() || res.getLast()[1] < cur[0]) {
            res.add(cur);
        } else {
            res.getLast()[1] = Math.max(res.getLast()[1], cur[1]);
        }
    }
    return res.toArray(new int[0][]);
}

时间复杂度：O(n log n)（排序主导）。

插入区间（LeetCode 57）

无需排序（已有序），分三阶段：不重叠-左、合并重叠、不重叠-右。

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> res = new ArrayList<>();
    int i = 0, n = intervals.length;
    // 1. 在新区间左侧的，直接加
    while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);
    // 2. 与新区间重叠的，合并
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.add(newInterval);
    // 3. 在新区间右侧的，直接加
    while (i < n) res.add(intervals[i++]);
    return res.toArray(new int[0][]);
}

会议室 I（LeetCode 252）

判断能否参加所有会议（无冲突）：按起点排序，检查相邻是否重叠。

public boolean canAttendMeetings(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i-1][1]) return false;
    }
    return true;
}

会议室 II（LeetCode 253）

最少需要多少间会议室：贪心 + 小根堆，堆中存结束时间。

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int[] m : intervals) {
        if (!heap.isEmpty() && heap.peek() <= m[0]) heap.poll();
        heap.offer(m[1]);
    }
    return heap.size();
}

无重叠区间（LeetCode 435）

移除最少区间使剩余不重叠（贪心：按结束时间排序，选结束早的）。

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] i : intervals) {
        if (i[0] >= end) {
            end = i[1];
        } else {
            count++;    // 需要移除当前区间
        }
    }
    return count;
}

总结