掃描線專題

leetcode 數(shù)組專題 06-掃描線算法（Sweep Line Algorithm）

leetcode 數(shù)組專題 06-leetcode.218 the-skyline-problem 力扣.218 天際線問(wèn)題

leetcode 數(shù)組專題 06-leetcode.252 meeting room 力扣.252 會(huì)議室

leetcode 數(shù)組專題 06-leetcode.253 meeting room ii 力扣.253 會(huì)議室 II

題目

給你一個(gè)會(huì)議時(shí)間安排的數(shù)組 intervals 迂曲，每個(gè)會(huì)議時(shí)間都會(huì)包括開(kāi)始和結(jié)束的時(shí)間 intervals[i] = [starti, endi] 碰缔，返回 所需會(huì)議室的最小數(shù)量 剩岳。

示例 1：

輸入：intervals = [[0,30],[5,10],[15,20]]
輸出：2

示例 2：

輸入：intervals = [[7,10],[2,4]]
輸出：1

提示：

1 <= intervals.length <= 10^4

0 <= starti < endi <= 10^6

整體思路

一般這種區(qū)間的題目赎线，常見(jiàn)的有下面的解決方案：

1. 暴力

2. 排序

3. 掃描線

4. 優(yōu)先隊(duì)列

不過(guò)這個(gè)感覺(jué)暴力不是很實(shí)用黔龟，不排序的話時(shí)間順序無(wú)法確定，會(huì)導(dǎo)致結(jié)果不正確毅舆。

v1-排序

思路

會(huì)議的開(kāi)始/結(jié)束時(shí)間吏饿，分別放在 2 個(gè)數(shù)組。然后對(duì)比笆怠。

如果不使用優(yōu)先隊(duì)列（最小堆）铝耻，而是只通過(guò) 排序 和 直接對(duì)比 來(lái)實(shí)現(xiàn)最小會(huì)議室數(shù)，思路可以是這樣的：

1. 排序：首先按照會(huì)議的開(kāi)始時(shí)間排序蹬刷，然后再按結(jié)束時(shí)間排序瓢捉。

2. 模擬會(huì)議室的分配：

   • 在同一時(shí)刻，檢查所有已安排的會(huì)議室是否有空余的办成。具體來(lái)說(shuō)泡态，當(dāng)一個(gè)會(huì)議開(kāi)始時(shí)，檢查是否有會(huì)議已經(jīng)結(jié)束（通過(guò)結(jié)束時(shí)間來(lái)判斷）迂卢。如果有空余的會(huì)議室某弦，就可以復(fù)用該會(huì)議室，否則需要額外增加一個(gè)會(huì)議室而克。

   • 通過(guò)維護(hù)一個(gè)結(jié)束時(shí)間列表來(lái)跟蹤當(dāng)前所有會(huì)議的結(jié)束時(shí)間靶壮。

3. 直接比較：

   • 對(duì)于每個(gè)會(huì)議，通過(guò)掃描結(jié)束時(shí)間列表判斷是否有會(huì)議結(jié)束员萍。如果有亮钦，則將其結(jié)束時(shí)間更新為當(dāng)前會(huì)議的結(jié)束時(shí)間；如果沒(méi)有結(jié)束的會(huì)議充活，說(shuō)明需要增加一個(gè)新的會(huì)議室蜂莉。

代碼實(shí)現(xiàn)：

我們不使用優(yōu)先隊(duì)列，直接通過(guò)兩個(gè)數(shù)組來(lái)實(shí)現(xiàn)混卵。

1. 排序會(huì)議的開(kāi)始時(shí)間映穗。
2. 通過(guò)一個(gè)循環(huán)遍歷會(huì)議，來(lái)模擬每次會(huì)議的安排過(guò)程幕随。

代碼實(shí)現(xiàn)：

import java.util.*;

public class MeetingRoomsII {
    public static int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        int n = intervals.length;

        // Step 1: Create two arrays to store the start and end times
        int[] startTimes = new int[n];
        int[] endTimes = new int[n];

        for (int i = 0; i < n; i++) {
            startTimes[i] = intervals[i][0];
            endTimes[i] = intervals[i][1];
        }

        // Step 2: Sort both start and end times
        Arrays.sort(startTimes);
        Arrays.sort(endTimes);

        int roomCount = 0;
        int endIndex = 0;

        // Step 3: Process each meeting one by one
        for (int i = 0; i < n; i++) {
            // If the current meeting starts after or when a meeting ends, reuse the room
            // 如果這一次開(kāi)始時(shí)間在上一次的結(jié)束之后蚁滋，則可以復(fù)用房間
            if (startTimes[i] >= endTimes[endIndex]) {
                // Reuse the room: move the endIndex to the next meeting
                endIndex++;
            } else {
                // If no room is available, we need a new one
                roomCount++;
            }
        }

        // The room count will be the number of rooms we need
        return roomCount + 1; // We need at least one room
    }
}

代碼解釋：

1. 排序：

   • 我們將所有的會(huì)議的開(kāi)始時(shí)間和結(jié)束時(shí)間分別存入 startTimes 和 endTimes 數(shù)組，并對(duì)這兩個(gè)數(shù)組進(jìn)行排序赘淮。這樣辕录，我們可以確保在處理會(huì)議時(shí)，始終按順序處理會(huì)議的開(kāi)始和結(jié)束時(shí)間梢卸。

2. 直接對(duì)比：

   • 我們使用一個(gè) endIndex 變量來(lái)跟蹤當(dāng)前最早結(jié)束的會(huì)議的結(jié)束時(shí)間走诞。
   • 對(duì)于每個(gè)會(huì)議（按開(kāi)始時(shí)間順序），我們判斷它是否可以復(fù)用當(dāng)前已經(jīng)結(jié)束的會(huì)議室：即蛤高，當(dāng)前會(huì)議的開(kāi)始時(shí)間是否大于等于最早結(jié)束會(huì)議的結(jié)束時(shí)間蚣旱。如果可以復(fù)用，我們將 endIndex 移動(dòng)到下一個(gè)結(jié)束的會(huì)議戴陡；如果不能復(fù)用塞绿，則說(shuō)明需要一個(gè)新的會(huì)議室。
   • roomCount 用于記錄會(huì)議室的數(shù)量恤批。

3. 返回值：

   • 最終返回 roomCount + 1异吻，因?yàn)槲覀冎辽傩枰粋€(gè)會(huì)議室來(lái)安排第一個(gè)會(huì)議。

v2-掃描線

思路

使用 掃描線算法 來(lái)解決 Leetcode 253 - 會(huì)議室 II 的問(wèn)題喜庞，是一種非常巧妙且高效的方法诀浪。

這個(gè)方法的核心思想是將所有的會(huì)議事件（開(kāi)始和結(jié)束）轉(zhuǎn)化為事件點(diǎn)，然后按時(shí)間順序處理這些事件赋荆，模擬會(huì)議室的使用情況笋妥。

思路：

1. 事件拆分：對(duì)于每個(gè)會(huì)議 interval[i] = [starti, endi]，我們將其拆解為兩個(gè)事件：

   • 開(kāi)始事件：表示一個(gè)新的會(huì)議室被占用窄潭。
   • 結(jié)束事件：表示一個(gè)會(huì)議室被釋放春宣。

2. 排序事件：所有的事件按時(shí)間進(jìn)行排序。需要注意：

   • 開(kāi)始事件：在相同的時(shí)間點(diǎn)嫉你，會(huì)議的開(kāi)始需要比結(jié)束事件優(yōu)先處理月帝。這是因?yàn)椋绻麅蓚€(gè)會(huì)議同時(shí)開(kāi)始和結(jié)束幽污，我們希望優(yōu)先安排新的會(huì)議嚷辅，而不是釋放會(huì)議室。

3. 掃描處理事件：掃描這些排序后的事件距误，使用一個(gè)變量來(lái)記錄當(dāng)前同時(shí)進(jìn)行的會(huì)議室數(shù)量簸搞，并更新最大會(huì)議室數(shù)量扁位。

   • 遇到開(kāi)始事件，會(huì)議室數(shù)增加趁俊。
   • 遇到結(jié)束事件域仇，會(huì)議室數(shù)減少。

4. 最大會(huì)議室數(shù)：掃描過(guò)程中維護(hù)一個(gè) maxRooms 變量來(lái)記錄需要的最大會(huì)議室數(shù)量寺擂。

詳細(xì)步驟：

1. 將每個(gè)會(huì)議拆分成開(kāi)始和結(jié)束兩個(gè)事件暇务。
2. 按照事件的時(shí)間進(jìn)行排序，如果時(shí)間相同怔软，則結(jié)束事件優(yōu)先垦细。
3. 掃描所有事件，計(jì)算同時(shí)進(jìn)行的會(huì)議數(shù)量挡逼，得到最大值括改。

掃描線算法實(shí)現(xiàn)：

import java.util.*;

public class MeetingRoomsII {
    public static int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        // Step 1: Create a list to store all events (start and end times)
        List<int[]> events = new ArrayList<>();
        for (int[] interval : intervals) {
            // Add start event
            events.add(new int[]{interval[0], 1});
            // Add end event
            events.add(new int[]{interval[1], -1});
        }

        // Step 2: Sort the events:
        // - First by time.
        // - If two events have the same time, prioritize end event (-1) over start event (1).
        events.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

        // Step 3: Scan the events and maintain the number of meeting rooms in use.
        int maxRooms = 0;
        int roomsInUse = 0;

        for (int[] event : events) {
            // Update the number of rooms in use
            roomsInUse += event[1];

            // Update the maximum number of rooms needed
            maxRooms = Math.max(maxRooms, roomsInUse);
        }

        return maxRooms;
    }
}

代碼解釋：

1. 事件轉(zhuǎn)換：

   • 對(duì)于每個(gè)會(huì)議 interval[i] = [starti, endi]，我們生成兩個(gè)事件：一個(gè)是開(kāi)始事件 starti挚瘟，表示需要一個(gè)會(huì)議室叹谁；另一個(gè)是結(jié)束事件 endi，表示釋放一個(gè)會(huì)議室乘盖。
   • 我們用 1 表示開(kāi)始事件焰檩，用 -1 表示結(jié)束事件，這樣在事件排序時(shí)可以通過(guò) -1 優(yōu)先處理結(jié)束事件订框，確保結(jié)束會(huì)議時(shí)會(huì)議室被釋放析苫。

2. 排序事件：

   • 首先根據(jù)時(shí)間排序。如果時(shí)間相同穿扳，我們優(yōu)先處理結(jié)束事件（-1）衩侥，因?yàn)槿绻麅蓚€(gè)會(huì)議同時(shí)開(kāi)始和結(jié)束，我們希望先釋放會(huì)議室矛物，再開(kāi)始新的會(huì)議茫死。

3. 掃描事件：

   • 初始化 roomsInUse 變量來(lái)記錄當(dāng)前正在使用的會(huì)議室數(shù)量。
   • 遍歷所有排序后的事件履羞，每次遇到開(kāi)始事件（1）峦萎，就增加 roomsInUse；每次遇到結(jié)束事件（-1）忆首，就減少 roomsInUse爱榔。
   • 同時(shí)，維護(hù)一個(gè) maxRooms 變量來(lái)記錄 roomsInUse 的最大值糙及，即最大會(huì)議室數(shù)量详幽。

時(shí)間復(fù)雜度：

• 事件拆分：我們有 N 個(gè)會(huì)議，每個(gè)會(huì)議生成兩個(gè)事件，因此總共有 2N 個(gè)事件唇聘，時(shí)間復(fù)雜度是 O(N)版姑。
• 排序：排序事件的時(shí)間復(fù)雜度是 O(2N log(2N))，也就是 O(N log N)雳灾。
• 掃描：掃描事件的時(shí)間復(fù)雜度是 O(2N)漠酿，也就是 O(N)。

因此谎亩，總的時(shí)間復(fù)雜度是 O(N log N)，主要由排序操作主導(dǎo)宇姚。

空間復(fù)雜度：

• 需要一個(gè)大小為 2N 的列表來(lái)存儲(chǔ)事件匈庭，空間復(fù)雜度是 O(N)。

小結(jié)

感覺(jué)掃描線挺有趣的浑劳，下一個(gè)系列我們就來(lái)學(xué)習(xí)一下這個(gè)掃描線專題算法阱持。

V3-優(yōu)先級(jí)隊(duì)列（最小堆）

思路：

最小堆可以用來(lái)模擬會(huì)議室的動(dòng)態(tài)分配，我們將會(huì)議的結(jié)束時(shí)間視為會(huì)議室的 "可用時(shí)間"魔熏，利用堆來(lái)維護(hù)當(dāng)前所有已分配的會(huì)議室的結(jié)束時(shí)間衷咽。

1. 排序會(huì)議的開(kāi)始時(shí)間：首先，我們將所有會(huì)議按照 開(kāi)始時(shí)間 排序蒜绽，這樣可以按順序處理會(huì)議镶骗。

2. 使用最小堆：我們使用一個(gè)最小堆來(lái)維護(hù)所有已分配會(huì)議室的結(jié)束時(shí)間。堆頂元素表示最早結(jié)束的會(huì)議躲雅。

   • 如果當(dāng)前會(huì)議的開(kāi)始時(shí)間大于或等于堆頂元素的結(jié)束時(shí)間鼎姊，說(shuō)明當(dāng)前會(huì)議可以復(fù)用堆頂?shù)臅?huì)議室。此時(shí)相赁，彈出堆頂元素（即釋放一個(gè)會(huì)議室）相寇，并將當(dāng)前會(huì)議的結(jié)束時(shí)間加入堆中。

   • 如果當(dāng)前會(huì)議的開(kāi)始時(shí)間小于堆頂元素的結(jié)束時(shí)間钮科，說(shuō)明需要新分配一個(gè)會(huì)議室唤衫，此時(shí)將當(dāng)前會(huì)議的結(jié)束時(shí)間加入堆中。

3. 堆的大小：堆的大小即為當(dāng)前所需的會(huì)議室數(shù)绵脯，最終堆的大小就是我們所需的最小會(huì)議室數(shù)佳励。

代碼

import java.util.*;

public class MeetingRoomsII {
    public static int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        // Step 1: Sort the meetings in increasing order of start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // Step 2: Create a min-heap to track the end times of meetings
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Step 3: Add the first meeting's end time to the heap
        minHeap.offer(intervals[0][1]);

        // Step 4: For all the remaining meetings
        for (int i = 1; i < intervals.length; i++) {
            // If the meeting can reuse the room, pop the earliest ending meeting
            if (intervals[i][0] >= minHeap.peek()) {
                minHeap.poll();
            }

            // Add the current meeting's end time to the heap
            minHeap.offer(intervals[i][1]);
        }

        // Step 5: The size of the heap is the minimum number of meeting rooms required
        return minHeap.size();
    }
}

代碼解釋

1. 排序會(huì)議開(kāi)始時(shí)間：

   • 我們首先按照會(huì)議的 開(kāi)始時(shí)間 對(duì)會(huì)議進(jìn)行排序。這樣可以確保我們處理會(huì)議時(shí)桨嫁，總是按開(kāi)始時(shí)間的順序來(lái)安排會(huì)議室植兰。

2. 最小堆（優(yōu)先隊(duì)列）：

   • 使用一個(gè)最小堆來(lái)維護(hù)已分配的會(huì)議室的結(jié)束時(shí)間。最小堆的堆頂始終是當(dāng)前最早結(jié)束的會(huì)議璃吧。
   • 每當(dāng)一個(gè)新會(huì)議到來(lái)時(shí)楣导，我們檢查當(dāng)前會(huì)議的開(kāi)始時(shí)間是否大于等于堆頂?shù)慕Y(jié)束時(shí)間，如果是畜挨，則可以復(fù)用一個(gè)會(huì)議室筒繁，彈出堆頂并將新會(huì)議的結(jié)束時(shí)間加入堆中噩凹。如果不能復(fù)用，則需要一個(gè)新的會(huì)議室毡咏，將新會(huì)議的結(jié)束時(shí)間加入堆中驮宴。

3. 堆的大小：

   • 最后，堆的大小即為所需的最小會(huì)議室數(shù)呕缭，因?yàn)槎训拿總€(gè)元素表示一個(gè)正在使用的會(huì)議室堵泽，堆的大小就是會(huì)議室的數(shù)量。

時(shí)間復(fù)雜度：

• 排序：排序會(huì)議的開(kāi)始時(shí)間的時(shí)間復(fù)雜度是 O(N log N)恢总，其中 N 是會(huì)議的數(shù)量迎罗。
• 堆操作：我們需要遍歷所有會(huì)議，對(duì)于每個(gè)會(huì)議執(zhí)行 poll 和 offer 操作片仿，這兩個(gè)操作的時(shí)間復(fù)雜度是 O(log N)纹安。
• 因此，總的時(shí)間復(fù)雜度是 O(N log N)砂豌，主要由排序和堆操作主導(dǎo)厢岂。

空間復(fù)雜度：

• 空間復(fù)雜度為 O(N)，用于存儲(chǔ)堆中的會(huì)議室結(jié)束時(shí)間阳距。最壞情況下塔粒，所有會(huì)議都需要一個(gè)單獨(dú)的會(huì)議室，堆的大小為 N娄涩。

本題中最小堆到底解決了什么問(wèn)題窗怒？

1. 會(huì)議室的結(jié)束時(shí)間是關(guān)鍵

每個(gè)會(huì)議都有一個(gè) 結(jié)束時(shí)間，我們只關(guān)心是否可以復(fù)用已分配的會(huì)議室蓄拣。

復(fù)用的前提是當(dāng)前會(huì)議的 開(kāi)始時(shí)間 要晚于或等于某個(gè)會(huì)議室的 結(jié)束時(shí)間扬虚。

• 如果當(dāng)前會(huì)議的 開(kāi)始時(shí)間 start[i] 大于等于某個(gè)會(huì)議室的 結(jié)束時(shí)間 end[j]，說(shuō)明該會(huì)議室在當(dāng)前時(shí)刻空閑球恤，可以被復(fù)用辜昵。
• 否則，我們就需要為當(dāng)前會(huì)議分配一個(gè)新的會(huì)議室咽斧。

2. 為什么使用最小堆堪置？

最小堆 的特點(diǎn)是能夠在 O(log N) 時(shí)間復(fù)雜度內(nèi)找出堆頂元素（最小值）。

在本題中张惹，我們使用最小堆來(lái)保持當(dāng)前正在使用的會(huì)議室的結(jié)束時(shí)間舀锨，并始終保持堆頂是最早結(jié)束的會(huì)議室。

這樣可以確保我們每次都能優(yōu)先復(fù)用最早結(jié)束的會(huì)議室宛逗。

如何利用最小堆來(lái)解決問(wèn)題坎匿？

最小堆的關(guān)鍵作用是幫助我們高效地跟蹤并更新最早結(jié)束的會(huì)議室：

• 添加會(huì)議室：每當(dāng)我們遇到一個(gè)新的會(huì)議時(shí)，我們將當(dāng)前會(huì)議的結(jié)束時(shí)間加入堆中。

• 檢查復(fù)用：每次處理一個(gè)新的會(huì)議時(shí)替蔬，我們檢查堆頂元素（即最早結(jié)束的會(huì)議室的結(jié)束時(shí)間）：

  • 如果當(dāng)前會(huì)議的開(kāi)始時(shí)間大于或等于堆頂?shù)慕Y(jié)束時(shí)間告私，則說(shuō)明我們可以復(fù)用這個(gè)會(huì)議室，彈出堆頂元素承桥，并將新的會(huì)議結(jié)束時(shí)間加入堆驻粟。
  • 如果不能復(fù)用（即當(dāng)前會(huì)議的開(kāi)始時(shí)間小于堆頂?shù)慕Y(jié)束時(shí)間），則我們需要為當(dāng)前會(huì)議分配一個(gè)新的會(huì)議室凶异，將新會(huì)議的結(jié)束時(shí)間加入堆中蜀撑。

4. 核心操作

• 堆頂元素的含義：堆頂元素表示當(dāng)前最早結(jié)束的會(huì)議室的結(jié)束時(shí)間。

通過(guò)彈出堆頂元素唠帝，我們可以將該會(huì)議室釋放出來(lái)屯掖，供下一次會(huì)議復(fù)用。

• 堆的大小：堆的大小即為當(dāng)前所需要的會(huì)議室數(shù)襟衰，最終堆的大小即為最小會(huì)議室數(shù)量。

小結(jié)

這一題我們的暴力算法是不太行的通的粪摘。

整體下來(lái)就是幾個(gè)主流思路：

1）排序+邏輯比較

2）排序+掃描線

3）排序+優(yōu)先級(jí)隊(duì)列

后面兩個(gè)為我們引入了新的知識(shí)點(diǎn)：掃描線+優(yōu)先級(jí)隊(duì)列瀑晒。

我們后面的專題就一起來(lái)學(xué)習(xí)一下。

開(kāi)源地址

為了便于大家學(xué)習(xí)徘意，所有實(shí)現(xiàn)均已開(kāi)源苔悦。歡迎 fork + star~

https://github.com/houbb/leetcode