Meeting Rooms

Given a list of meeting intervals, represented as pairs of integers [start, end], where start denotes the start time of the meeting and end denotes the end time of the meeting, determine if a person can attend all meetings without any overlaps.

Example:

Input:

meetings = [[1, 5], [8, 10], [3, 6], [15, 18]]

Output:

false

Explanation: In the input, the person cannot attend all meetings without overlaps. The meeting interval [1, 5] and [3, 6] overlap, so it is not possible to attend both meetings without conflicts.

Meeting Rooms Solution in C++:

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

// Function to check if a person can attend all meetings
bool canAttendMeetings(std::vector<std::vector<int>>& meetings) {
    // Sort the meetings based on their start time in ascending order
    std::sort(meetings.begin(), meetings.end(), [](const auto& a, const auto& b) {
        return a[0] < b[0];
    });

    // Check for any overlapping meetings
    for (int i = 1; i < meetings.size(); ++i) {
        if (meetings[i][0] < meetings[i - 1][1]) {
            return false; // Overlapping meetings found
        }
    }

    return true; // No overlapping meetings
}

int main() {
    std::vector<std::vector<int>> meetings = {{1, 5}, {8, 10}, {3, 6}, {15, 18}};

    bool result = canAttendMeetings(meetings);

    std::cout << "Can attend all meetings without overlaps: " << (result ? "true" : "false") << std::endl;

    return 0;
}

Meeting Rooms Explanation:

1. The canAttendMeetings function takes a reference to a vector of vectors meetings.
2. We sort the meetings vector based on their start time in ascending order using a custom comparator. This helps us identify overlapping meetings efficiently.
3. We then iterate through the sorted meetings vector and check if any two consecutive meetings have overlapping times. If the start time of the current meeting (meetings[i][0]) is less than the end time of the previous meeting (meetings[i - 1][1]), it means the meetings overlap.
4. If we find any overlapping meetings during the iteration, we return false, indicating that the person cannot attend all meetings without conflicts.
5. If we reach the end of the loop without finding any overlaps, it means the person can attend all meetings without conflicts, and we return true.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the number of meetings in the input vector meetings. The main factor in the time complexity is the sorting step, which takes O(n log n) time using std::sort.

Space Complexity:

The space complexity of this solution is O(1). We use a constant amount of additional space for variables and the sorting is done in-place within the given vector meetings.