区间问题（合并区间 · 插入区间 · 会议室）

合并区间（LeetCode 56）

排序后，逐个检查当前区间与上一个是否重叠：

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.get(res.size() - 1)[1] < cur[0]) {
            res.add(cur);  // 不重叠，直接加入
        } else {
            // 重叠，合并右端点
            res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], cur[1]);
        }
    }
    return res.toArray(new int[0][]);
}

插入区间（LeetCode 57）

已排序且不重叠的区间列表中插入一个新区间，分三段处理：

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）

判断能否参加所有会议（区间是否有重叠）：

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）

最少需要多少个会议室（最多同时进行的会议数）：

小根堆贪心：按开始时间排序，堆中存每个会议室当前会议的结束时间。如果最早结束的会议已经结束，复用该会议室；否则新开一间。

int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();  // 最早结束的会议室

    for (int[] interval : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll();  // 复用这个会议室
        }
        endTimes.offer(interval[1]);
    }
    return endTimes.size();
}

差分数组解法（适合端点离散或询问区间覆盖次数）：

int minMeetingRooms2(int[][] intervals) {
    // 将开始/结束分别排序
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts); Arrays.sort(ends);

    int rooms = 0, j = 0;
    for (int i = 0; i < n; i++) {
        if (starts[i] < ends[j]) rooms++;   // 需要新房间
        else j++;                           // 有房间空出来
    }
    return rooms;
}

划分字母区间（LeetCode 763）

贪心：每个字母只在一个片段中出现，且片段尽可能小。

List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;

    List<Integer> res = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);
        if (i == end) {
            res.add(end - start + 1);
            start = end + 1;
        }
    }
    return res;
}