每日算法 — 使用java实现扫描线：矩形面积并与会议室调度

扫描线（Sweep Line）算法是计算几何领域的经典技巧，通过将二维问题降维到一维来处理。本文以”会议室调度”和”矩形面积并”两个经典场景为例，深入讲解扫描线算法的核心思想与Java实现。

算法核心思想

扫描线算法的本质是利用事件驱动的思想：想象一条垂直的扫描线从左向右移动，遇到矩形的左边界时”激活”该矩形，遇到右边界时”关闭”该矩形。通过维护当前被激活的区间集合，我们可以在每个事件点快速计算所需的信息。

核心步骤：
1. 事件提取：将所有边界转化为带有方向的事件（进入/离开）
2. 事件排序：按坐标排序，决定扫描线的移动顺序
3. 状态维护：使用线段树或有序集合维护当前激活区间
4. 区间聚合：计算当前激活区间的总长度或重叠情况

场景一：会议室调度（区间最大重叠数）

问题描述

给定一组会议时间区间，求同一时刻最多需要多少个会议室。

算法思路

将每个会议的开始时间和结束时间视为事件：
– 开始时间：会议室需求+1
– 结束时间：会议室需求-1

按时间顺序扫描所有事件，维护当前需要的会议室数量，取最大值即可。

Java实现

import java.util.*;

/**
 * 会议室调度问题：计算同一时刻最多需要的会议室数量
 * 使用扫描线算法，时间复杂度 O(n log n)
 */
public class MeetingRoomScheduler {

    /**
     * 会议事件：时间点和变化量（+1表示开始，-1表示结束）
     */
    static class Event implements Comparable<Event> {
        int time;      // 事件发生时间
        int delta;     // 会议室数量变化（+1 或 -1）

        Event(int time, int delta) {
            this.time = time;
            this.delta = delta;
        }

        @Override
        public int compareTo(Event other) {
            // 时间相同时，结束事件优先处理（先释放再占用）
            if (this.time != other.time) {
                return this.time - other.time;
            }
            return this.delta - other.delta; // -1（结束）在 +1（开始）之前
        }
    }

    /**
     * 计算最少需要的会议室数量
     * @param intervals 会议时间区间数组，intervals[i] = [开始时间, 结束时间]
     * @return 同时进行的最多会议数（即最少会议室数）
     */
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        List<Event> events = new ArrayList<>();

        // 步骤1：提取所有事件
        for (int[] interval : intervals) {
            events.add(new Event(interval[0], 1));   // 会议开始
            events.add(new Event(interval[1], -1));  // 会议结束
        }

        // 步骤2：按时间排序事件
        Collections.sort(events);

        // 步骤3：扫描线遍历，维护当前会议室使用数量
        int currentRooms = 0;
        int maxRooms = 0;

        for (Event event : events) {
            currentRooms += event.delta;
            maxRooms = Math.max(maxRooms, currentRooms);
        }

        return maxRooms;
    }

    /**
     * 扩展功能：返回具体每个会议室安排了哪些会议
     */
    public List<List<int[]>> scheduleMeetings(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new ArrayList<>();
        }

        // 按开始时间排序会议
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // 优先队列：按结束时间排序，存储每个会议室的最后结束时间
        PriorityQueue<int[]> rooms = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        // 记录每个会议分配到哪个会议室
        int[] assignment = new int[intervals.length];

        for (int i = 0; i < intervals.length; i++) {
            int[] meeting = intervals[i];

            // 检查是否有会议室已空闲（结束时间 <= 当前会议开始时间）
            if (!rooms.isEmpty() && rooms.peek()[0] <= meeting[0]) {
                int[] room = rooms.poll();
                assignment[i] = room[1];  // 复用该会议室
                rooms.offer(new int[]{meeting[1], room[1]});
            } else {
                // 需要新会议室
                assignment[i] = rooms.size();
                rooms.offer(new int[]{meeting[1], rooms.size()});
            }
        }

        // 按会议室分组输出
        List<List<int[]>> result = new ArrayList<>();
        for (int i = 0; i < rooms.size(); i++) {
            result.add(new ArrayList<>());
        }
        for (int i = 0; i < intervals.length; i++) {
            result.get(assignment[i]).add(intervals[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        MeetingRoomScheduler scheduler = new MeetingRoomScheduler();

        // 测试用例
        int[][] intervals = {
            {0, 30}, {5, 10}, {15, 20}
        };

        System.out.println("=== 会议室调度问题 ===");
        System.out.println("会议区间: " + Arrays.deepToString(intervals));
        System.out.println("最少需要会议室: " + scheduler.minMeetingRooms(intervals));

        // 更复杂的测试
        int[][] intervals2 = {
            {1, 5}, {2, 6}, {3, 7}, {8, 10}, {9, 12}
        };
        System.out.println("\\n会议区间: " + Arrays.deepToString(intervals2));
        System.out.println("最少需要会议室: " + scheduler.minMeetingRooms(intervals2));

        // 打印具体安排
        System.out.println("\\n=== 会议室具体安排 ===");
        List<List<int[]>> schedule = scheduler.scheduleMeetings(intervals2);
        for (int i = 0; i < schedule.size(); i++) {
            System.out.println("会议室 " + (i + 1) + ": " + schedule.get(i));
        }
    }
}

场景二：矩形面积并

问题描述

给定多个轴对齐矩形（由左下角和右上角坐标定义），求它们覆盖的总面积（重叠部分只算一次）。

算法思路

1. 离散化Y坐标：收集所有矩形的上下边界Y坐标，排序去重
2. 事件提取：每个矩形的左右边作为事件，记录Y区间范围
3. 线段树维护：用线段树维护当前Y轴上被覆盖的长度
4. 扫描计算：从左到右扫描，相邻X事件之间的面积 = 覆盖长度 × X间距

Java实现

import java.util.*;

/**
 * 矩形面积并问题：计算多个矩形覆盖的总面积
 * 使用扫描线 + 线段树 + 坐标离散化，时间复杂度 O(n log n)
 */
public class RectangleAreaUnion {

    /**
     * 垂直边事件
     */
    static class Edge implements Comparable<Edge> {
        int x;           // 边的X坐标
        int y1, y2;      // Y区间范围
        int type;        // +1 左边（进入），-1 右边（离开）

        Edge(int x, int y1, int y2, int type) {
            this.x = x;
            this.y1 = y1;
            this.y2 = y2;
            this.type = type;
        }

        @Override
        public int compareTo(Edge other) {
            return this.x - other.x;
        }
    }

    /**
     * 线段树节点：维护区间覆盖信息
     */
    static class SegTree {
        int[] cover;     // 区间被完全覆盖的次数
        int[] length;    // 区间内实际被覆盖的长度
        int[] ys;        // 离散化后的Y坐标数组

        SegTree(int[] ys) {
            this.ys = ys;
            int n = ys.length;
            // 需要4倍空间，叶子节点代表区间 [ys[i], ys[i+1])
            cover = new int[n * 4];
            length = new int[n * 4];
        }

        /**
         * 更新区间 [y1, y2) 的覆盖次数
         */
        void update(int node, int l, int r, int y1, int y2, int val) {
            if (y1 >= ys[r] || y2 <= ys[l]) {
                return; // 无交集
            }

            if (y1 <= ys[l] && ys[r] <= y2) {
                // 完全覆盖
                cover[node] += val;
            } else {
                int mid = (l + r) >> 1;
                update(node << 1, l, mid, y1, y2, val);
                update(node << 1 | 1, mid, r, y1, y2, val);
            }

            // 更新当前节点的覆盖长度
            if (cover[node] > 0) {
                // 被完全覆盖，长度为整个区间
                length[node] = ys[r] - ys[l];
            } else if (l + 1 == r) {
                // 叶子节点且未被覆盖
                length[node] = 0;
            } else {
                // 合并子节点信息
                length[node] = length[node << 1] + length[node << 1 | 1];
            }
        }
    }

    /**
     * 计算矩形面积并
     * @param rectangles 每个矩形为 [x1, y1, x2, y2]，表示左下角(x1,y1)到右上角(x2,y2)
     * @return 总面积
     */
    public int rectangleArea(int[][] rectangles) {
        if (rectangles == null || rectangles.length == 0) {
            return 0;
        }

        final int MOD = 1_000_000_007;
        List<Edge> edges = new ArrayList<>();
        Set<Integer> ySet = new TreeSet<>();

        // 步骤1：提取所有边事件和Y坐标
        for (int[] rect : rectangles) {
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            edges.add(new Edge(x1, y1, y2, 1));
            edges.add(new Edge(x2, y1, y2, -1));
            ySet.add(y1);
            ySet.add(y2);
        }

        // 步骤2：离散化Y坐标
        int[] ys = new int[ySet.size()];
        int idx = 0;
        for (int y : ySet) {
            ys[idx++] = y;
        }

        // 步骤3：按X排序事件
        Collections.sort(edges);

        // 步骤4：构建线段树并扫描
        SegTree segTree = new SegTree(ys);
        long area = 0;
        long prevX = edges.get(0).x;

        for (Edge edge : edges) {
            long x = edge.x;
            // 计算前一个X区间形成的面积
            area += segTree.length[1] * (x - prevX);
            area %= MOD;

            // 更新当前边对应的Y区间
            segTree.update(1, 0, ys.length - 1, edge.y1, edge.y2, edge.type);
            prevX = x;
        }

        return (int) area;
    }

    public static void main(String[] args) {
        RectangleAreaUnion solver = new RectangleAreaUnion();

        // 测试用例1：两个重叠矩形
        int[][] rectangles1 = {
            {0, 0, 2, 2},
            {1, 1, 3, 3}
        };
        System.out.println("=== 矩形面积并 ===");
        System.out.println("矩形列表: " + Arrays.deepToString(rectangles1));
        System.out.println("总面积: " + solver.rectangleArea(rectangles1)); // 预期: 7

        // 测试用例2：多个矩形
        int[][] rectangles2 = {
            {0, 0, 2, 2},
            {1, 0, 2, 3},
            {1, 0, 3, 1}
        };
        System.out.println("\\n矩形列表: " + Arrays.deepToString(rectangles2));
        System.out.println("总面积: " + solver.rectangleArea(rectangles2)); // 预期: 6
    }
}

复杂度分析

扫描线算法的适用场景

扫描线算法特别适用于以下类型的问题：
– 区间统计：最大重叠数、区间覆盖长度
– 几何计算：矩形面积/周长并、最近点对（一维扫描）
– 事件模拟：时间轴上的状态变化追踪
– 碰撞检测：在一维投影上快速筛选候选碰撞对

掌握扫描线算法的核心在于理解“降维”思想——将复杂的二维/多维问题，通过在某一维度上的有序扫描，转化为可维护的一维区间问题。