Meeting Scheduler

You are given the availability of two people’s schedules, represented as lists of intervals [start, end]. Each interval represents the available time for each person, and it is a closed interval (inclusive) denoting the time the person is available for a meeting.

Your task is to find a common time slot of duration duration that is available for both people to schedule a meeting. If such a time slot exists, return the starting time of the slot; otherwise, return an empty list.

Example:

Input:

person1 = [[10, 50], [60, 120], [140, 210]]
person2 = [[0, 15], [60, 70]]
duration = 8

Output:

[60, 68]

Explanation: In the input, the available time for person 1 is [[10, 50], [60, 120], [140, 210]] and for person 2 is [[0, 15], [60, 70]]. The duration of the meeting required is 8. The common time slot for both people to schedule the meeting is [60, 68], which has a duration of 8.

Meeting Scheduler Solution in C++:

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

// Function to find a common time slot for scheduling a meeting
std::vector<int> meetingScheduler(std::vector<std::vector<int>>& person1, std::vector<std::vector<int>>& person2, int duration) {
    // Sort both person's schedules based on their start time in ascending order
    std::sort(person1.begin(), person1.end(), [](const auto& a, const auto& b) {
        return a[0] < b[0];
    });
    std::sort(person2.begin(), person2.end(), [](const auto& a, const auto& b) {
        return a[0] < b[0];
    });

    int i = 0;
    int j = 0;

    // Traverse both schedules to find a common time slot
    while (i < person1.size() && j < person2.size()) {
        int start = std::max(person1[i][0], person2[j][0]);
        int end = std::min(person1[i][1], person2[j][1]);

        if (end - start >= duration) {
            return {start, start + duration}; // Found a common time slot
        }

        // Move to the next interval for the person whose interval ends first
        if (person1[i][1] < person2[j][1]) {
            ++i;
        } else {
            ++j;
        }
    }

    return {}; // No common time slot found
}

int main() {
    std::vector<std::vector<int>> person1 = {{10, 50}, {60, 120}, {140, 210}};
    std::vector<std::vector<int>> person2 = {{0, 15}, {60, 70}};
    int duration = 8;

    std::vector<int> result = meetingScheduler(person1, person2, duration);

    if (!result.empty()) {
        std::cout << "Common time slot for meeting: [" << result[0] << ", " << result[1] << "]\n";
    } else {
        std::cout << "No common time slot found for the given duration.\n";
    }

    return 0;
}

Explanation:

1. The meetingScheduler function takes references to two vectors of vectors person1 and person2, representing their available schedules, and an integer duration denoting the duration of the required meeting.
2. We sort both person’s schedules based on their start time in ascending order using custom comparators. This helps us efficiently traverse their schedules.
3. We initialize two pointers, i and j, to 0, representing the current index for person1 and person2, respectively.
4. We traverse both schedules using a while loop until we reach the end of either schedule.
5. For each pair of intervals, [start1, end1] from person1, and [start2, end2] from person2, we find the common time slot using the formula:
   start = max(start1, start2)
end = min(end1, end2)
6. If the duration of the common time slot (end - start) is greater than or equal to the required meeting duration, we have found a valid time slot, and we return it.
7. If the duration is not sufficient, we move to the next interval for the person whose interval ends first.
8. After processing all intervals, if we don’t find a valid time slot, we return an empty list.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the total number of intervals in both person1 and person2. The main factors in the time complexity are the sorting steps (O(n log n)) for both schedules.

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 vectors person1 and person2. The returned vector for the common time slot also has a constant size of 2.