Skip to content
AI360Xpert
Back to Intervals
Medium

Meeting Rooms II

Given an array of meeting time intervals `intervals` where `intervals[i] = [starti, endi]`, return the minimum number of conference rooms required.

Examples

Input:intervals = [[0,30],[5,10],[15,20]]
Output:2
We need one room for [0,30]. Since [5,10] and [15,20] overlap with [0,30] but not with each other, they can share the second room.
Input:intervals = [[7,10],[2,4]]
Output:1
Since the meetings do not overlap, only one room is needed.

Constraints

  • 1 <= intervals.length <= 10^4
  • 0 <= starti < endi <= 10^6

Chronological Ordering (Two Pointers)

Approach

Instead of treating the start and end times as a single interval, we can separate them. Sort all the start times into one array and all the end times into another array. Use two pointers, one for the start array and one for the end array. Iterate through the start times: - If `start[s] < end[e]`, it means a meeting has started before the earliest ending meeting has finished. We need a new room, so we increment our room count and move the `s` pointer. - If `start[s] >= end[e]`, it means a meeting has finished before or exactly when the next one starts. A room just became free, so we decrement our room count, and move the `e` pointer. We keep track of the maximum number of rooms needed at any point.

Complexity Analysis

Time Complexity
O(n log n)
Space Complexity
O(n)

Time complexity is O(n log n) because we sort the start and end arrays. The two-pointer iteration takes O(n). Space complexity is O(n) to store the separated start and end arrays.

Solution.java
class Solution {    public int minMeetingRooms(int[][] intervals) {        if (intervals == null || intervals.length == 0) return 0;                int n = intervals.length;        int[] starts = new int[n];        int[] ends = new int[n];                for (int i = 0; i < n; i++) {            starts[i] = intervals[i][0];            ends[i] = intervals[i][1];        }                Arrays.sort(starts);        Arrays.sort(ends);                int rooms = 0;        int maxRooms = 0;        int s = 0;        int e = 0;                while (s < n) {            if (starts[s] < ends[e]) {                rooms++;                s++;            } else {                rooms--;                e++;            }            maxRooms = Math.max(maxRooms, rooms);        }                return maxRooms;    }}