Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [(s1,e1),(s2,e2),...] (si < ei), determine if a person could attend all meetings.

Approach#

• Intuition: Two meetings conflict if and only if one starts before the other ends. After sorting by start time, any conflict will always be between two adjacent intervals — a later interval can only conflict with the one immediately before it in sorted order, never with one further back.
• Mechanics: Sort the intervals by start time. Then scan linearly; if any interval's start time is strictly less than the previous interval's end time, a conflict exists and the person cannot attend all meetings.
• Trade-off: Sorting reduces an O(n²) pairwise comparison problem to an O(n log n) sort followed by a single O(n) pass. No extra data structure is needed beyond the sort itself.

bool canAttendMeetings(vector<vector<int>> &intervals)
{
    sort(intervals.begin(), intervals.end());

    for(int i=1;i<intervals.size();i++)
    {
        if(intervals[i][0] < intervals[i-1][1])
            return false;
    }
    return true;
}

Time Complexity: O(N * logN)

Space Complexity: O(N)