跳到主要内容

区间问题

问题​

Java 中区间相关的常见算法题有哪些？

答案​

区间题的核心：排序 + 贪心/扫描线。

合并区间（LeetCode 56）​

按起点排序后贪心合并
public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            merged.get(merged.size() - 1)[1] = 
                Math.max(merged.get(merged.size() - 1)[1], interval[1]);
        }
    }
    return merged.toArray(new int[0][]);
}

插入区间（LeetCode 57）​

三段处理：左边不重叠 + 合并重叠 + 右边不重叠
public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;
    
    // 1. 左边不重叠的
    while (i < n && intervals[i][1] < newInterval[0]) result.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++;
    }
    result.add(newInterval);
    
    // 3. 右边不重叠的
    while (i < n) result.add(intervals[i++]);
    
    return result.toArray(new int[0][]);
}

会议室（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> minHeap = new PriorityQueue<>();  // 存各会议室最早结束时间
    
    for (int[] interval : intervals) {
        if (!minHeap.isEmpty() && minHeap.peek() <= interval[0]) {
            minHeap.poll();  // 复用会议室
        }
        minHeap.offer(interval[1]);
    }
    return minHeap.size();
}

用最少数量的箭引爆气球（LeetCode 452）​

按结束位置排序，贪心射箭
public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1;
    int end = points[0][1];
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > end) {  // 新气球超出当前箭的范围
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
}

常见面试问题​

Q1: 区间题的通用解题思路？​

答案：

  1. 排序：按起点或终点排序
  2. 遍历：逐个处理区间，判断重叠关系
  3. 贪心：根据题意选择合并/移除/计数

Q2: 按起点排序 vs 按终点排序？​

答案：

排序方式适用场景
按起点排序合并区间、插入区间、会议室
按终点排序无重叠区间（贪心选最早结束的）、射箭

相关链接​