Question

How to find the common free time for all employees from a vector of non-overlapping intervals in C++

Answer 1

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

using std::vector;
using std::pair;

/*
 * Find common free time:
 * 1. Sort intervals
 * 2. Merge overlapping intervals
 * 3. Gaps between merged intervals are free time
 */
vector<pair<int,int>> findCommonFreeTime(vector<pair<int,int>>& intervals) {
    // 1. Sort by start time
    std::sort(intervals.begin(), intervals.end());

    // 2. Merge intervals
    vector<pair<int,int>> merged;
    merged.push_back(intervals[0]);

    for (int i = 1; i < intervals.size(); i++) {
        auto& last = merged.back();
        if (intervals[i].first <= last.second) {
            last.second = std::max(last.second, intervals[i].second);
        } else {
            merged.push_back(intervals[i]);
        }
    }

    // 3. Find gaps (free time)
    vector<pair<int,int>> freeTime;
    for (int i = 1; i < merged.size(); i++) {
        int start = merged[i-1].second;
        int end   = merged[i].first;
        if (start < end)
            freeTime.emplace_back(start, end);
    }

    return freeTime;
}

int main() {
    vector<pair<int,int>> intervals = {{2,3},{4,5},{7,11},{1,5},{6,9}};
    auto freeTime = findCommonFreeTime(intervals);

    for (auto &p : freeTime)
        std::cout << "[" << p.first << "," << p.second << "] ";
}


/*
run:

[5,6] 

*/

 

70+ SQL courses for beginners and professionals