Meeting Rooms easy

Problem Statement

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1

Input: intervals = [[0,30],[5,10],[15,20]] Output: false Explanation: Since the intervals [5,10] and [15,20] overlap, the person cannot attend all meetings.

Example 2

Input: intervals = [[7,10],[2,4]] Output: true Explanation: The intervals do not overlap.

Steps

1. Sort the intervals: Sort the intervals based on their start times. This allows us to efficiently check for overlaps by iterating through the sorted list.

2. Iterate and check for overlaps: Iterate through the sorted intervals. For each interval, compare its start time with the end time of the previous interval. If the current interval's start time is less than or equal to the previous interval's end time, there's an overlap, and we can return false.

3. Return true: If the loop completes without finding any overlaps, it means all meetings can be attended, and we return true.

Explanation

The core idea is that if we sort the intervals by their start times, we only need to check if consecutive intervals overlap. If any consecutive intervals overlap, then it's impossible to attend all meetings. Sorting guarantees that we only need to compare adjacent elements.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool canAttendMeetings(vector<vector<int>>& intervals) {
    // Sort intervals by start time
    sort(intervals.begin(), intervals.end());

    // Iterate through sorted intervals and check for overlaps
    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false; // Overlap detected
        }
    }

    return true; // No overlaps found
}

int main() {
    vector<vector<int>> intervals1 = {{0, 30}, {5, 10}, {15, 20}};
    vector<vector<int>> intervals2 = {{7, 10}, {2, 4}};

    cout << "Can attend all meetings (Example 1): " << canAttendMeetings(intervals1) << endl; // Output: false
    cout << "Can attend all meetings (Example 2): " << canAttendMeetings(intervals2) << endl; // Output: true

    return 0;
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step. N is the number of intervals.
• Space Complexity: O(1) (or O(log N) if the sorting algorithm used requires extra space, depending on the implementation of std::sort). The space used is constant excluding the space for the input array.