253. Meeting Rooms II.md

253. Meeting Rooms II

Tag

• Array, Two Pointers
• Amazon, Google, Bloomberg, Facebook, Microsoft

Description

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: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

Solution

Two Pointers & Chronological Ordering

• We use two pointers to simulate the following scan process (using the relative position between two pointers)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length; // total num of meetings
        // Create collections of meeting starting time & ending time
        int[] start = new int[n];
        int[] end = new int[n];
        // Fill in starting time and ending time
        for (int i = 0; i < n; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        // Sort the times
        Arrays.sort(start);
        Arrays.sort(end);
        // Init
        int max = 0;
        int count = 0;
        // Two pointers in start and end 
        int i = 0, j = 0;
        while (i < n && j < n) {
            if (start[i] < end[j]) { // Case 1: a new meeting started
                count++;
                i++;
            } else { // Case 2: a meeting ended
                count--;
                j++;
            }
            // Check if current num of rooms hits a peek
            max = Math.max(max, count);
        }
        return max;
    }
}

• TC: O(n * log n)
  • dominate by the sorting process
• SC: O(n)