253. Meeting Rooms II
https://leetcode.com/problems/meeting-rooms-ii/
---
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
Example 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2Example 2:
Input: [[7,10],[2,4]] Output: 1
Intuition
Need to count the max number of overlaps
Wrapper class - int time, boolean isStart
Sort by time, if time is same => need to release the room first => Boolean.compare(a.isStart, b.isStart)
Iterate through the sorted list of wrapper class
if start
rooms++
else
room--
ans= max(ans, rooms)
---
Time - O(N log N)
Space - O(N)
---
Related problems
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Event { | |
| int time; | |
| boolean isStart; | |
| public Event(int t, boolean s) { | |
| time = t; | |
| isStart = s; | |
| } | |
| } | |
| class Solution { | |
| public int minMeetingRooms(int[][] intervals) { | |
| if (intervals == null || intervals.length == 0) { | |
| return 0; | |
| } | |
| List<Event> list = new ArrayList<Event>(); | |
| for (int[] i: intervals) { | |
| list.add(new Event(i[0], true)); | |
| list.add(new Event(i[1], false)); | |
| } | |
| // if time stamps are same, keep end time first to release rooms first | |
| Collections.sort(list, (a, b) -> a.time == b.time ? Boolean.compare(a.isStart, b.isStart) : Integer.compare(a.time, b.time)); | |
| int ans = 0, rooms = 0; | |
| for (Event e: list) { | |
| if (e.isStart) { | |
| rooms++; | |
| ans = Math.max(ans, rooms); | |
| } else { | |
| rooms--; | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def minMeetingRooms(self, intervals: List[List[int]]) -> int: | |
| events = [] | |
| for interval in intervals: | |
| events.append((interval[0], True)) | |
| events.append((interval[1], False)) | |
| events = sorted(events) | |
| opened, closed, ans = 0, 0, 0 | |
| for event in events: | |
| if event[1]: | |
| opened += 1 | |
| ans = max(ans, opened) | |
| else: | |
| opened -= 1 | |
| return ans |
