Meeting Rooms Check If A Person Can Attend All Meetings In C++

Introduction:

The C++ "Meeting Rooms" challenge involves verifying if an individual can participate in all planned meetings without any time overlaps. Each meeting is defined by a time range, including both the beginning and ending times. The objective is to assess if there are any scheduling conflicts among the meetings.

Suppose multiple appointments are scheduled throughout the day, each with a defined start and end time. If there is any overlap between two appointments, it will not be possible for the individual to participate in both. The task at hand is to analyze these time intervals and determine if the individual can attend all appointments without any scheduling conflicts.

Key Concept: Interval Overlap

A meeting interval is defined by [start, end], where:

The start denotes the commencement time of the meeting.

The end represents the conclusion time of the meeting (exclusive, allowing the next meeting to start at the precise end time of the previous one).

Two intervals are considered to have an overlap if and only if a meeting commences prior to the conclusion of the preceding meeting. In the scenario of two intervals represented by [start1, end1] and [start2, end2], an overlap is determined by the condition where the starting time of the second interval (start2) is less than the ending time of the first interval (end1).

To prevent clashes, it is important to make sure that there are no overlapping schedules for any two meetings.

Approach 1: Naive Approach

Implementation:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
    int start;
    int end;
};
bool canAttendMeetings(vector<Interval>& meetings) {
    // Step 1: Sort meetings based on the start time
    sort(meetings.begin(), meetings.end(), [](const Interval& a, const Interval& b) {
        return a.start < b.start;
    });
    // Step 2: Check for overlapping meetings
    for (size_t i = 1; i < meetings.size(); ++i) {
        // If the start of the current meeting is less than the end of the previous meeting, return false
        if (meetings[i].start < meetings[i - 1].end) {
            return false;
        }
    }
    return true;
}
int main() {
    vector<Interval> meetings = {{1, 3}, {2, 4}, {5, 6}};
    if (canAttendMeetings(meetings)) {
        cout << "Yes, the person can attend all meetings." << endl;
    } else {
        cout << "No, the person cannot attend all meetings." << endl;
    }
    return 0;
}

Output:

No, the person cannot attend all meetings.

Explanation:

Step 1: Structuring the Problem

The initial task involves acknowledging that every meeting is defined by a specific start time and end time. These time frames are viewed as intervals, symbolizing the duration of each meeting. The challenge lies in determining if there are any intersections among these intervals, indicating a scheduling conflict where an individual cannot be present for two concurrent meetings.

Step 2: Sorting the Meetings

To simplify the process of detecting overlaps, the meetings are organized in ascending order according to their starting times. Sorting is beneficial as it arranges the meetings in a manner that guarantees each meeting is compared with the subsequent one in a sequential manner. Consequently, after sorting, it becomes necessary to only assess each meeting against its adjacent meeting, thereby decreasing the overall complexity of the task.

Step 3: Detecting Overlap

Once the time intervals are organized in ascending order based on their starting times, the subsequent action involves verifying if there are any intersections. An overlap is identified when a meeting initiates prior to the conclusion of the preceding meeting.

For instance:

• ✅ Imagine having two appointments: one scheduled from 1 PM to 3 PM and another from 2 PM to 4 PM. The latter meeting commences at 2 PM, preceding the conclusion of the former at 3 PM, resulting in a clash where both meetings overlap, making it impossible for the individual to participate in both.

Step 4: Iterating Through the Meetings

After sorting, you move through the list of meetings one by one:

• ✅ Start by comparing the second meeting's start time with the first meeting's end time.
• ✅ If the start time of the second meeting is less than the end time of the first, an overlap is found, and you can immediately conclude that the person can't attend all meetings.
• ✅ If no overlap is detected, continue to compare the next pair of meetings, moving through the list.

Step 5: Returning the Result

The objective is to iterate through the complete roster of meetings, analyzing consecutive time frames. In case an intersection is detected at any stage, the function promptly outputs "false," signifying the inability to attend all sessions. Successfully navigating the entire list without encountering any overlaps results in the function returning "true," affirming the feasibility of attending all meetings.

Complexity analysis:

Time Complexity:

Sorting the Intervals:

The initial crucial step involves arranging the collection of meeting intervals based on their start times. Sorting typically operates at O(nlogn) complexity, with n representing the count of intervals (or meetings). This stands out as the primary element affecting the time complexity, given that sorting constitutes the most time-consuming segment of the operation.

Checking for Overlaps:

After arranging the intervals in order, the subsequent task involves traversing through the arranged intervals to identify any overlaps. This process entails moving through the list once, resulting in a time complexity of O(n). Each interval is assessed against the preceding one, making this phase operate with a linear complexity.

Due to the prominence of the sorting process, the total time complexity sums up to O(nlogn).

Space Complexity:

In-place Sorting:

If the sorting method applied is an in-place sort (like the std::sort function in C++), it does not require any extra space for sorting apart from a fixed amount of additional memory. Consequently, the sorting process consumes O(1) additional space.

Input Storage:

The intervals are saved in a list, requiring O(n) space as there are n intervals.

Auxiliary Space:

The portion of the algorithm responsible for checking overlapping intervals relies on a limited number of variables to retain indices and assess intervals, resulting in constant space complexity, denoted as O(1).

Thus, the total space complexity is O(n) as a result of storing the input intervals. There is no additional space required for sorting or verification purposes beyond the initial storage.

Approach 2: Using a Min-Heap (Priority Queue)

This approach guarantees effective handling of scheduling conflicts by prioritizing the meeting with the earliest end time, enabling us to assess the feasibility of attending a new meeting.

Implementation:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>  // Include this for sort()
using namespace std;
struct Interval {
    int start;
    int end;
};
// Comparator to sort intervals by their start time
bool compare(const Interval& a, const Interval& b) {
    return a.start <  b.start;
}
bool canAttendMeetings(vector<Interval>& meetings) {
    if (meetings.empty()) {
        return true;
    }
    // Step 1: Sort the meetings by start time
    sort(meetings.begin(), meetings.end(), compare);
    // Step 2: Use a min-heap (priority queue) to track the end times of meetings
    priority_queue<int, vector<int>, greater<int>> minHeap;
    // Step 3: Push the end time of the first meeting into the heap
    minHeap.push(meetings[0].end);
    // Step 4: Iterate through the rest of the meetings
    for (size_t i = 1; i < meetings.size(); ++i) {
        // Check if the current meeting starts after the earliest ended meeting
        if (meetings[i].start >= minHeap.top()) {
            // Remove the meeting that ended earliest
            minHeap.pop();
        }
        // Add the current meeting's end time to the heap
        minHeap.push(meetings[i].end);
    }
    // If the heap contains only one meeting at the end, all meetings were attended
    return minHeap.size() == 1;
}
int main() {
    vector<Interval> meetings = {{1, 3}, {2, 4}, {5, 6}};
    if (canAttendMeetings(meetings)) {
        cout << "Yes, the person can attend all meetings." << endl;
    } else {
        cout << "No, the person cannot attend all meetings." << endl;
    }
    return 0;
}

Output:

No, the person cannot attend all meetings.

Explanation:

Step 1: Problem Understanding

We have multiple meetings, each characterized by a specific start and end time. The objective is to determine if an individual can participate in all these meetings consecutively without any time overlaps. This strategy involves the dynamic organization of meeting schedules to enable efficient verification of potential conflicts with existing appointments.

Step 2: Sorting the Meetings by Start Time

The initial step involves organizing the meetings according to their start times. By sorting the meetings in this manner, it guarantees that each meeting will only be compared with the one that directly follows it in the sequence. This step is crucial as it facilitates the identification of any conflicts between two sessions, making it more straightforward to detect when they are examined consecutively. The ordered list of meetings serves as the groundwork for subsequent actions.

Step 3: Employing a Min-Heap to Monitor the Earliest Completion Time.

To effectively handle the conclusion times of meetings, a priority queue, which is essentially a min-heap, is employed. This data structure ensures access to the smallest element, representing the meeting with the earliest end time. This functionality is crucial as identifying the meeting that concludes first allows for prompt evaluation of whether the following meeting can commence thereafter or if there exists a scheduling conflict.

Initially, the finishing time of the initial meeting is inserted into the min-heap. This allows us to monitor the completion time of the first meeting.

Step 4: Processing Each Meeting

Now, for each subsequent meeting:

• ✅ You compare the start time of the current meeting with the earliest end time of any ongoing meeting (the one at the top of the min-heap).
• ✅ If the current meeting starts after or at the same time the earliest meeting ends, there's no conflict, and the earliest-ended meeting can be removed from the heap. This signifies that the earlier meeting is over, and the current meeting can proceed without any overlap.
• ✅ After that, you add the current meeting's end time to the heap, which signify that this meeting is now in progress and will potentially overlap with future meetings.

Step 5: Checking for Overlaps

The heap is structured to store the conclusion times of active meetings. If the heap expands excessively or when numerous meetings coincide temporally, it indicates a scenario where the individual cannot participate in all meetings. In particular, if a meeting commences prior to the conclusion of the earliest meeting, it results in a scheduling conflict.

If, after processing all meetings, there remains only a single meeting in the heap, it signifies that every meeting was managed without any clashes, enabling the individual to participate in all of them.

Complexity analysis:

Time Complexity

Sorting the Meetings:

Arranging the meeting list in order of their starting times stands out as the most time-intensive task within this strategy. The common sorting algorithm employed, such as std::sort, exhibits a time complexity of O(nlogn), with n representing the total count of meetings.

Processing Meetings with the Min-Heap:

• ✅ After sorting, the algorithm processes each meeting once. For each meeting, it performs two primary operations: Inserting an end time into the min-heap: This operation takes O(logk) time, where k is the number of elements currently in the heap. In the worst case, k can be up to n, making the insertion operation O(logn). Removing the smallest end time from the min-heap: This operation also takes O(logk) time, which, in the worst case, is O(logn).
• ✅ As each meeting is processed once and we perform these operations at most n times, the total time complexity for processing all meetings with the heap is O(nlogn).
• ✅ Inserting an end time into the min-heap: This operation takes O(logk) time, where k is the number of elements currently in the heap. In the worst case, k can be up to n, making the insertion operation O(logn).
• ✅ Removing the smallest end time from the min-heap: This operation also takes O(logk) time, which, in the worst case, is O(logn).

The primary time complexity is O(nlogn) due to the dominant sorting of meetings, with heap operations contributing a logarithmic factor.

Space Complexity

Space for Sorting:

Sorting takes place within the existing memory allocation, requiring minimal extra space that remains constant regardless of the input list size. This results in a space complexity of O(1) for the sorting process alone, excluding the space needed for the initial list.

Space allocated for the Min-Heap:

The minimum heap is utilized to store the concluding times of active meetings. In the most unfavorable scenario, the heap may have to accommodate the concluding times of all meetings concurrently, demanding O(n) space.

Space for Storing Input Data:

The list of appointments necessitates O(n) space to keep track of the time intervals.

The total space complexity is O(n), considering the storage needed for both the input list and the heap data structure.

Approach 3: Using sweep line algorithm

The sweep line technique entails handling a sequence of occurrences by simulating a vertical line moving from the left to the right along a timeline. When applied to scheduling meetings, the objective is to ascertain whether an individual can participate in all meetings without any scheduling conflicts.

Implementation:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
enum EventType { START, END };
struct Event {
    int time;
    EventType type;
    bool operator<(const Event& other) const {
        if (time == other.time) {
            return type < other.type;  // Ensure that end events are processed before start events if they have the same time
        }
        return time < other.time;
    }
};
bool canAttendMeetings(vector<pair<int, int>>& meetings) {
    vector<Event> events;
    // Convert meetings to events
    for (const auto& meeting : meetings) {
        events.push_back({meeting.first, START});
        events.push_back({meeting.second, END});
    }
    // Sort events by time and type
    sort(events.begin(), events.end());
    int ongoingMeetings = 0;
    // Process events
    for (const auto& event : events) {
        if (event.type == START) {
            ongoingMeetings++;
            if (ongoingMeetings > 1) {
                return false;  // Overlap detected
            }
        } else {
            ongoingMeetings--;
        }
    }
    return true;  // No overlaps detected
}
int main() {
    vector<pair<int, int>> meetings = {{1, 3}, {2, 4}, {5, 6}};
    if (canAttendMeetings(meetings)) {
        cout << "Yes, the person can attend all meetings." << endl;
    } else {
        cout << "No, the person cannot attend all meetings." << endl;
    }
    return 0;
}

Output:

No, the person cannot attend all meetings.

Explanation:

Convert Meetings into Events:

• ✅ Each meeting is represented by two key moments in time: the start time and the end time. To apply the sweep line algorithm, these moments are converted into discrete events.
• ✅ For each meeting, you create two events:
• ✅ Start Event: Occurs when the meeting begins.
• ✅ End Event: Occurs when the meeting ends.

To effectively manage these occurrences, they are organized according to their timestamps. The key factor in arranging them is the timing of the event. In cases where two events share the same timestamp, concluding events take precedence over initiating events. This is essential to ensure that if a meeting concludes and another begins simultaneously, the conclusion is addressed before the initiation to prevent inaccurate overlap identification.

Process the Events:

• ✅ As you process each event in the sorted order, you maintain a counter to keep track of the number of ongoing meetings.
• ✅ Handling Start Events: Each time a start event is encountered, increment the counter. This signifies that a new meeting has begun and is now overlapping with ongoing meetings.
• ✅ Handling End Events: Each time an end event is encountered, decrement the counter. This signifies that a meeting has concluded, reducing the count of ongoing meetings.

Detect Overlaps:

• ✅ During event processing, continuously monitor the counter:
• ✅ If the counter exceeds one at any point, it means there are overlapping meetings. Consequently, the person cannot attend all meetings without a conflict.
• ✅ If the counter remains at one or less throughout the process, it indicates that all meetings are scheduled in such a way that they do not overlap, allowing attendance at all meetings.

Complexity analysis:

Time Complexity

Event Creation:

• ✅ Every single meeting results in the generation of two events - one marking the beginning and the other indicating the conclusion. Hence, with a total of n meetings, the number of events produced will be 2n.
• ✅ The process of creating these events operates in O(n) time complexity, as each meeting adds a consistent workload to the overall generation task.

Arranging the events requires O(mlogm) time complexity, with m representing the total events. As m is equivalent to 2n (two events for each meeting), the sorting process operates at O(nlogn). Sorting stands out as the most time-intensive phase within this method.

Processing Events:

• ✅ Each event processing requires incrementing a counter and validating certain criteria. As every event is handled only once, this operation has a time complexity of O(m), where m represents the total number of events, resulting in O(n) time complexity in this scenario.

Combining these actions, the primary time complexity is determined by the sorting phase: O(nlogn)

Space Complexity

Event Storage:

To retain all the occurrences, it is essential to have a storage mechanism in place. Given that n meetings produce 2n events, the storage space needed is proportional to n, denoted as O(n).

Additional Variables:

• ✅ Room is essential for accommodating the counter and several other variables; however, these necessitate consistent space allocation.

Input Storage:

• ✅ Storing the initial list of meetings consumes O(n) space.

Merging these, the total space complexity amounts to O(n).