Blind 75
Meeting Rooms II
- Problem
- LC 253
- Category
- Interval
- File
- blind75_LC253MeetingRoomsII.java
- Path
- pkg5leetcode/blind75/blind75_LC253MeetingRoomsII.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC253MeetingRoomsII.java
- Approach
- Min-heap of end times; reuse room if earliest ends before start.
- Complexity
- Time O(n log n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Meeting Rooms II | LC 2535 * APPROACH: Min-heap of end times; reuse room if earliest ends before start.6 * COMPLEXITY: Time O(n log n), Space O(n)7 */8import java.util.*;9 10public class blind75_LC253MeetingRoomsII {11 static int minMeetingRooms(int[][] intervals) {12 if (intervals.length == 0) return 0;13 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));14 PriorityQueue<Integer> heap = new PriorityQueue<>();15 heap.add(intervals[0][1]);16 for (int i = 1; i < intervals.length; i++) {17 if (intervals[i][0] >= heap.peek()) heap.poll();18 heap.add(intervals[i][1]);19 }20 return heap.size();21 }22 23 public static void main(String[] args) {24 check(minMeetingRooms(new int[][]{{0, 30}, {5, 10}, {15, 20}}) == 2, "case1");25 check(minMeetingRooms(new int[][]{{7, 10}, {2, 4}}) == 1, "case2");26 System.out.println("all tests passed");27 }28 29 static void check(boolean cond, String name) {30 if (!cond) throw new AssertionError("FAILED: " + name);31 System.out.println(" PASS " + name);32 }33}