Employee Free Time

You are given a list of employees’ working hours as a list of intervals. Each interval represents the working hours of an employee, and it is a closed interval [start, end] (inclusive) denoting the time the employee started and finished work.

Your task is to find the periods during which all employees are free. In other words, find the common free time across all employees.

Example:

Input:

schedule = [
    [[1, 3], [6, 7]],
    [[2, 4]],
    [[2, 5], [9, 12]]
]

Output:

[[5, 6], [7, 9]]

Explanation: In the input, the working hours for three employees are given as intervals: [[1, 3], [6, 7]], [[2, 4]], and [[2, 5], [9, 12]]. The common free time across all employees is the time range from 5 to 6 and from 7 to 9.

Employee Free Time Solution in C++:

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

// Function to find employee free time
std::vector<std::vector<int>> employeeFreeTime(std::vector<std::vector<std::vector<int>>>& schedule) {
    std::vector<std::vector<int>> result;
    std::vector<std::pair<int, int>> events;

    // Convert all working hours into events and store them in the events vector
    for (const auto& empSchedule : schedule) {
        for (const auto& interval : empSchedule) {
            events.push_back({interval[0], 1}); // Start of work, represented by 1
            events.push_back({interval[1], -1}); // End of work, represented by -1
        }
    }

    // Sort the events vector in ascending order of time and type
    std::sort(events.begin(), events.end(), [](const auto& a, const auto& b) {
        return a.first < b.first || (a.first == b.first && a.second > b.second);
    });

    int active = 0;
    int prev = -1;

    // Iterate through the events vector to find the free time intervals
    for (const auto& event : events) {
        if (active == 0 && prev != -1) {
            result.push_back({prev, event.first});
        }
        active += event.second;
        prev = event.first;
    }

    return result;
}

int main() {
    std::vector<std::vector<std::vector<int>>> schedule = {
        {{1, 3}, {6, 7}},
        {{2, 4}},
        {{2, 5}, {9, 12}}
    };

    std::vector<std::vector<int>> result = employeeFreeTime(schedule);

    std::cout << "Employee Free Time:\n";
    for (const auto& interval : result) {
        std::cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    std::cout << std::endl;

    return 0;
}

Employee Free Time Explanation:

1. The employeeFreeTime function takes a reference to a vector of vectors of vectors schedule, representing the working hours of employees.
2. We create a new vector result to store the free time intervals.
3. We create a new vector events to store all working hours as events, represented by pairs of integers. We use 1 to denote the start of work and -1 to denote the end of work.
4. We convert all working hours into events and store them in the events vector.
5. We sort the events vector in ascending order based on time. If two events have the same time, we sort them such that the start of work (1) comes before the end of work (-1). This allows us to handle overlapping intervals properly.
6. We iterate through the sorted events vector and maintain a variable active to keep track of the number of employees currently working. We also use a variable prev to store the end time of the last interval that was processed.
7. If active becomes 0, it means that all employees are not working, and there is a free time interval. We add the free time interval to the result vector.
8. After processing all events, the result vector will contain the common free time intervals across all employees.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the total number of working hours in the input vector schedule. 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(n), where n is the total number of working hours in the input vector schedule. This is because we use the events vector to store all working hours as events, which has a size of 2 times the number of working hours. The result vector also has a size proportional to the number of free time intervals. In the worst case, if there are no overlapping intervals, the size of both vectors is equal to the number of working hours.