253. 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.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

Solution:

We split the input array to two arrays: one with all the start points and the other with all the end points.

Sort these two arrays.

Use two pointers point to two arrays and compare each element.

If we find start time is less than end time, we know we need one more room.

If we find start time is larger than end time, we know we can release a room

We keep a max value of the rooms we need.

The time complexity is O(nlogn) since we use sort.



Code:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int maxRoom = 0;
        int room = 0;
        int i = 0;
        int j = 0;
        while (i < starts.length) {
            if (starts[i] < ends[j]) {
                room++;
                maxRoom = Math.max(maxRoom, room);
                i++;
            }
            else if (starts[i] > ends[j]) {
                room--;
                j++;
            }
            else {
                i++;
                j++;
            }
        }
        return maxRoom;
    }
}