Given an array of meeting time intervals, return the minimum number of conference rooms required.
Input: [[0,30],[5,10],[15,20]] → Output: 2Input: [[7,10],[2,4]] → Output: 1
Use separate sorted arrays of start and end times. Two pointers: when next start < current end, we need a new room; otherwise we reuse one.
- Extract and sort starts[] and ends[] separately.
- i=0 (start pointer), j=0 (end pointer), rooms=0, maxRooms=0.
- For each start: if starts[i] < ends[j]: rooms++, i++; else j++, rooms--, i++. Actually: if starts[i]
- Track max rooms.
import java.util.*;
class Solution {
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n], 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, maxRooms = 0, j = 0;
for (int i = 0; i < n; i++) {
if (starts[i] < ends[j]) rooms++;
else { rooms--; j++; }
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)