LC: 253. Meeting Rooms II
https://leetcode.com/problems/meeting-rooms-ii/
253. Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1Constraints:
1 <= intervals.length <= 1040 <= starti < endi <= 106
The Essence: Wir können einfach alle möglichen Fälle denken:
Wenn es nur 1 Meeting gibt, brauchen wir nur 1 Raum.
Wenn es mehr als 1 Meeting gibt und die nächsten Meetings nach dem Ende des Vorherigen beginnen, brauchen wir wieder nur 1 Zimmer. (d. h. im Fall ohne Überlappungen).
Wenn ein Meeting endet, nachdem ein Meeting mit einer späteren Startzeit begonnen hat, weist dies auf Überlappungen hin.
Daraus kann gefolgert werden, dass für jedes Intervall mehrere Räume benötigt wird, wenn das aktuelle früheste Endzeit größer als die Startzeit ist.
Details:
Da die angegebenen Intervalle nicht sortiert sind, erfordert die Verwendung dieses Verfahrens entweder Sortierung und Prioritätsschlangen, wobei Endzeiten und Startzeiten getrennt werden müssen. Für den Fall der Array-Sortierung ist auch eine Zwei-Zeiger-Technik für die beiden Arrays nützlich.
Solution(s) and Further Explanation:
Further explanation and code can be found here:
Default Code:
Last updated