Meeting Rooms II

Problem

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of rooms required to schedule all meetings without any conflicts.

Note: (0,8),(8,10) is NOT considered a conflict at 8.

Examples

Example 1:

Input: intervals = [(0,40),(5,10),(15,20)]

Output: 2

Explanation:

• room1: (0,40)
• room2: (5,10),(15,20)

Example 2:

Input: intervals = [(4,9)]

Output: 1

Constraints

• 0 <= intervals.length <= 500
• 0 <= intervals[i].start < intervals[i].end <= 1,000,000

You should aim for a solution with O(nlogn) time and O(n) space, where n is the size of the input array.

Solution

Sort start and end times, but track whether its a start or end time. Tie breaking goes to end times first. Then, we just loop over the times and increment for every start and decrement for every end.

/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */
 
class Solution {
    struct Time {
        int time;
        bool is_start;
    };
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        // Trivial base case
        if (intervals.size() <= 1) { return intervals.size(); }
 
        std::vector<Time> times;
        times.reserve(intervals.size() * 2);
        for (const auto &interval : intervals) {
            times.emplace_back(interval.start, true);
            times.emplace_back(interval.end, false);
        }
        
        // Sort based on time, and end time coming before start of tiebreaking
        std::ranges::sort(times, 
            [&](const auto &lhs, const auto &rhs) -> bool {
                return lhs.time < rhs.time || 
                       (lhs.time == rhs.time && lhs.is_start < rhs.is_start);
            }
        );
 
        int count = 0;
        int max_count = 0;
        for (const auto &time : times) {
            count += time.is_start ? 1 : -1;
            max_count = std::max(max_count, count);
        }
        return max_count;
    }
};