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.

The Idea: My first thought was to think about this problem in terms of interval scheduling. If we were to for example, optimize for the number most schedules we can fit, then that would be equivelent in saying that the intervals can all occupy the same room, since they do not conflict. Then solution would then follow as the number of conferences - opt.max + 1. This however will not work. Consider the counter example:

input: [[4, 9], [2, 15], [16, 23], [48, 29], [36, 45]]
solution: 2
our output: 3

Imagine if we were to take on this challenge in the real world. How would we take on the job manually? First, we would take all the conferences that will be going on that day, and sort this depending on who will be going first. Because we have to support all the conferences, we take them as they go and when they are needed. Using a priority_queue we can manage all the conferences that are currently going on. Lets call this queue the support. First, add the first conference in to the support, then beging iterating through the remainder of the conferences. If it so happens that the next conference does not conflict with the conference that was going on, we can remove the conference in the support and add in the new one. However, if there is a conflict, we'll have to open up a new room, and add this new conference into our support. When there are two or more conferences going on, we'll want to priotize the conference that will end the earliest. Because of the heap ordering of our support this will imply that the top will always be at least a good as the remainding conferences going on.

In the end the remaining conferences in our support will the total rooms we'll have to support considering all the conferences that went on.

Complexity: O(nlogn + n) time and O(n) space

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

int minMeetingRooms(vector<Interval>& intervals) {
    if (intervals.empty())
        return 0;

    sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {
        return a.start < b.start;
    });

    auto comp = [](Interval a, Interval b) { return a.end > b.end; };
    priority_queue<Interval, vector<Interval>, decltype(comp)> support(comp);
    support.push(intervals.front());

    for (auto i = intervals.begin() + 1; i != intervals.end(); i++) {
        if (i->start >= support.top().end) 
            support.pop();
        support.push(*i);
    }

    return support.size();
}