每日算法 — 使用java实现区间合并：贪心策略与重叠区间调度优化

区间问题是算法竞赛和工程实践中非常常见的题型。从会议安排、资源分配到基因序列比对，区间合并与调度算法的应用无处不在。本文将深入讲解区间合并的核心思想，用Java实现经典算法，并扩展到区间调度、区间覆盖等变体问题。

一、问题定义与场景分析

1.1 区间合并问题

给定一组闭区间 [start, end]，要求合并所有重叠的区间，返回互不重叠的区间集合。

例如：
– 输入：[[1,3], [2,6], [8,10], [15,18]]
– 输出：[[1,6], [8,10], [15,18]]

重叠判定：两个区间 [a,b] 和 [c,d] 重叠，当且仅当 a <= d && c <= b。

1.2 区间调度问题

给定一组区间，选择尽可能多的互不重叠区间。这是经典的贪心问题，最优策略是按结束时间排序，每次选择结束最早且不与已选区间冲突的区间。

1.3 区间覆盖问题

给定目标区间 [L,R] 和一组候选区间，选择最少数量的候选区间完全覆盖目标区间。

二、核心算法设计

2.1 区间合并算法

1. 按区间左端点升序排序
2. 维护当前合并区间 [currStart, currEnd]
3. 遍历排序后的区间：
4. 若当前区间与合并区间重叠，扩展合并区间的右端点
5. 若不重叠，将合并区间加入结果，开始新的合并区间
6. 遍历结束后加入最后一个合并区间

时间复杂度：O(n log n)，主要来自排序

2.2 区间调度贪心证明

按结束时间排序后，设第一个区间为最优解的一部分。对于剩余区间，选择结束最早且不冲突的区间不会比任何其他选择更差。形式化证明使用交换论证：假设最优解未选该区间，则可用该区间替换最优解中与之冲突的区间，得到另一个最优解。

2.3 区间覆盖贪心算法

1. 筛选出与目标区间 [L,R] 有交集的候选区间
2. 按左端点排序
3. 在每次选择中，从当前覆盖点出发，选择右端点最远且左端点不超过当前覆盖点的区间
4. 更新当前覆盖点为所选区间的右端点
5. 重复直到覆盖 [L,R] 或无法继续

三、Java完整实现

import java.util.*;

/**
 * 区间合并与调度算法实现
 * 包含区间合并、区间调度、区间覆盖等经典问题
 */
public class IntervalMerge {

    /**
     * 区间类，使用不可变设计
     */
    static class Interval implements Comparable<Interval> {
        final int start;
        final int end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        /**
         * 判断两个区间是否重叠
         */
        boolean overlaps(Interval other) {
            return this.start <= other.end && other.start <= this.end;
        }

        /**
         * 合并两个重叠区间
         */
        Interval merge(Interval other) {
            return new Interval(
                Math.min(this.start, other.start),
                Math.max(this.end, other.end)
            );
        }

        @Override
        public int compareTo(Interval other) {
            return Integer.compare(this.start, other.start);
        }

        @Override
        public String toString() {
            return "[" + start + ", " + end + "]";
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Interval)) return false;
            Interval that = (Interval) o;
            return start == that.start && end == that.end;
        }

        @Override
        public int hashCode() {
            return Objects.hash(start, end);
        }
    }

    /**
     * 区间合并：合并所有重叠区间
     * @param intervals 输入区间列表
     * @return 合并后的区间列表
     */
    public static List<Interval> mergeIntervals(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return new ArrayList<>(intervals);
        }

        // 按左端点排序
        List<Interval> sorted = new ArrayList<>(intervals);
        Collections.sort(sorted);

        List<Interval> result = new ArrayList<>();
        Interval current = sorted.get(0);

        for (int i = 1; i < sorted.size(); i++) {
            Interval next = sorted.get(i);
            if (current.overlaps(next)) {
                // 重叠，扩展当前区间
                current = current.merge(next);
            } else {
                // 不重叠，保存当前区间，开始新区间
                result.add(current);
                current = next;
            }
        }
        result.add(current); // 加入最后一个区间

        return result;
    }

    /**
     * 区间调度：选择尽可能多的互不重叠区间
     * 贪心策略：按结束时间排序，每次选择结束最早且不冲突的区间
     */
    public static List<Interval> maxNonOverlapping(List<Interval> intervals) {
        if (intervals == null || intervals.isEmpty()) {
            return new ArrayList<>();
        }

        // 按结束时间升序排序
        List<Interval> sorted = new ArrayList<>(intervals);
        sorted.sort(Comparator.comparingInt((Interval i) -> i.end)
                             .thenComparingInt(i -> i.start));

        List<Interval> result = new ArrayList<>();
        Interval lastSelected = null;

        for (Interval interval : sorted) {
            if (lastSelected == null || interval.start > lastSelected.end) {
                result.add(interval);
                lastSelected = interval;
            }
        }

        return result;
    }

    /**
     * 区间覆盖：用最少数量的区间覆盖目标区间 [targetStart, targetEnd]
     * @return 最少区间数，若无法覆盖返回 -1
     */
    public static int minIntervalsToCover(List<Interval> intervals,
                                           int targetStart, int targetEnd) {
        // 筛选与目标区间有交集的候选区间，并按左端点排序
        List<Interval> candidates = new ArrayList<>();
        for (Interval iv : intervals) {
            if (iv.end >= targetStart && iv.start <= targetEnd) {
                candidates.add(iv);
            }
        }
        candidates.sort(Comparator.comparingInt((Interval i) -> i.start)
                                   .thenComparingInt(i -> -i.end)); // 左端点相同选右端点大的

        int count = 0;
        int currentEnd = targetStart;
        int i = 0;
        int n = candidates.size();

        while (currentEnd < targetEnd) {
            int maxReach = currentEnd;
            // 选择所有左端点不超过currentEnd的区间中，右端点最远的
            while (i < n && candidates.get(i).start <= currentEnd) {
                maxReach = Math.max(maxReach, candidates.get(i).end);
                i++;
            }

            if (maxReach == currentEnd) {
                return -1; // 无法继续覆盖
            }

            currentEnd = maxReach;
            count++;
        }

        return count;
    }

    /**
     * 查找所有区间中的交集区间（公共重叠部分）
     */
    public static List<Interval> findIntersections(List<Interval> intervals) {
        if (intervals == null || intervals.size() < 2) {
            return new ArrayList<>();
        }

        // 使用扫描线算法
        List<int[]> events = new ArrayList<>();
        for (Interval iv : intervals) {
            events.add(new int[]{iv.start, 1});  // 开始事件
            events.add(new int[]{iv.end, -1});   // 结束事件
        }

        events.sort((a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            return Integer.compare(b[1], a[1]); // 结束事件优先于开始事件（处理点区间）
        });

        List<Interval> intersections = new ArrayList<>();
        int active = 0;
        int intersectStart = -1;

        for (int[] event : events) {
            if (event[1] == 1) {
                active++;
                if (active == intervals.size()) {
                    intersectStart = event[0];
                }
            } else {
                if (active == intervals.size()) {
                    intersections.add(new Interval(intersectStart, event[0]));
                }
                active--;
            }
        }

        return intersections;
    }

    /**
     * 插入新区间到已合并的区间列表中
     */
    public static List<Interval> insertInterval(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        int i = 0;
        int n = intervals.size();

        // 添加所有在newInterval之前的区间
        while (i < n && intervals.get(i).end < newInterval.start) {
            result.add(intervals.get(i));
            i++;
        }

        // 合并所有与newInterval重叠的区间
        Interval merged = newInterval;
        while (i < n && intervals.get(i).start <= merged.end) {
            merged = merged.merge(intervals.get(i));
            i++;
        }
        result.add(merged);

        // 添加剩余的区间
        while (i < n) {
            result.add(intervals.get(i));
            i++;
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println("=== 区间合并与调度算法演示 ===\n");

        // 1. 区间合并
        List<Interval> intervals = Arrays.asList(
            new Interval(1, 3),
            new Interval(2, 6),
            new Interval(8, 10),
            new Interval(15, 18),
            new Interval(5, 9)
        );
        System.out.println("原始区间: " + intervals);
        List<Interval> merged = mergeIntervals(intervals);
        System.out.println("合并结果: " + merged + "\n");

        // 2. 区间调度
        List<Interval> scheduleIntervals = Arrays.asList(
            new Interval(1, 3),
            new Interval(2, 4),
            new Interval(3, 5),
            new Interval(6, 8),
            new Interval(8, 10)
        );
        System.out.println("调度候选: " + scheduleIntervals);
        List<Interval> selected = maxNonOverlapping(scheduleIntervals);
        System.out.println("最多可选 " + selected.size() + " 个区间: " + selected + "\n");

        // 3. 区间覆盖
        List<Interval> coverIntervals = Arrays.asList(
            new Interval(1, 4),
            new Interval(2, 5),
            new Interval(6, 8),
            new Interval(7, 10),
            new Interval(9, 12)
        );
        int minCover = minIntervalsToCover(coverIntervals, 1, 12);
        System.out.println("覆盖 [1, 12] 最少需要 " + minCover + " 个区间\n");

        // 4. 区间交集
        List<Interval> intersectTest = Arrays.asList(
            new Interval(1, 10),
            new Interval(3, 8),
            new Interval(5, 12)
        );
        List<Interval> common = findIntersections(intersectTest);
        System.out.println("三个区间的公共交集: " + common + "\n");

        // 5. 插入区间
        List<Interval> mergedList = Arrays.asList(
            new Interval(1, 2),
            new Interval(3, 5),
            new Interval(6, 7),
            new Interval(8, 10),
            new Interval(12, 16)
        );
        Interval toInsert = new Interval(4, 9);
        List<Interval> afterInsert = insertInterval(mergedList, toInsert);
        System.out.println("在 " + mergedList + " 中插入 " + toInsert);
        System.out.println("结果: " + afterInsert);
    }
}

四、算法复杂度分析

五、工程应用场景

1. 会议管理系统：合并连续会议，找出空闲时间段
2. 基因序列分析：合并重叠的基因片段，找出保守区域
3. CDN缓存预热：合并相邻的缓存失效区间，批量预热
4. 数据库分区维护：合并相邻的小分区，优化查询性能
5. 任务调度系统：在资源约束下最大化并行任务数量

六、总结

区间问题是贪心算法的经典应用场景。本文实现的核心算法包括：

• 区间合并：排序后线性扫描，O(n log n) 时间合并所有重叠区间
• 区间调度：按结束时间贪心选择，证明其最优性
• 区间覆盖：每次选择能覆盖最远端点的区间，达到最少数量
• 扫描线算法：通过事件驱动处理多区间交集问题

掌握这些基础算法后，可以应对绝大多数区间相关问题。关键在于将实际问题抽象为区间模型，并选择恰当的贪心策略。