Meeting Rooms

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), determine if a person could add all meetings to their schedule without any conflicts. The intervals may be provided in any order.

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

Examples

Example 1:

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

Output: false

Explanation:

• (0,30) and (5,10) will conflict
• (0,30) and (15,20) will conflict

Example 2:

Input: intervals = [(5,8),(9,15)]

Output: true

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 based on start time, then iterate comparing pairwise adjacent intervals to see if an overlap occurs.

/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */
 
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        // Trivial base case
        if (intervals.size() <= 1) { return true; }
        // Sort based on start times
        std::ranges::sort(intervals, 
            [&](const auto &lhs, const auto &rhs) -> bool {
                return lhs.start < rhs.start; 
            }
        );
        // Try to find a conflict
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i].start < intervals[i-1].end) {
                return false;
            }
        }
        return true;
    }
};