#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    int start;
    int end;
};

// Comparison function to sort intervals by start time.
bool compareIntervals(const Interval &a, const Interval &b) {
    return a.start < b.start;
}

// Two-pointer filtering: Remove meeting intervals that overlap with any not-available interval.
vector<Interval> filterMeetings(const vector<Interval>& meetings, const vector<Interval>& notAvail) {
    vector<Interval> result;
    int m = meetings.size(), n = notAvail.size();
    int i = 0, j = 0;

    while (i < m) {
        // Advance j until we find a not-available interval that might overlap.
        while (j < n && notAvail[j].end < meetings[i].start) {
            j++;
        }

        bool overlaps = false;
        // Check if the current meeting overlaps with the current not-available interval.
        if (j < n && notAvail[j].start <= meetings[i].end) {
            overlaps = true;
        }

        if (!overlaps) {
            result.push_back(meetings[i]);
        }
        i++;
    }
    return result;
}

// Merge overlapping meeting intervals.
vector<Interval> mergeIntervals(const vector<Interval>& intervals) {
    if (intervals.empty()) return {};
    vector<Interval> merged;
    Interval current = intervals[0];
    for (size_t i = 1; i < intervals.size(); i++) {
        // If the next interval overlaps or touches the current one, merge them.
        if (intervals[i].start <= current.end) {
            current.end = max(current.end, intervals[i].end);
        } else {
            merged.push_back(current);
            current = intervals[i];
        }
    }
    merged.push_back(current);
    return merged;
}

int main(){
    // Example Input:
    // Meeting intervals (each as [start, end])
    vector<Interval> meetings = {
        {9, 10},
        {9, 11},
        {13, 14}
    };

    // Not-available intervals
    vector<Interval> notAvailable = {
        {10, 10} // For example, the person is not available at time 10.
    };

    // Sort both lists by start time
    sort(meetings.begin(), meetings.end(), compareIntervals);
    sort(notAvailable.begin(), notAvailable.end(), compareIntervals);

    // Filter meetings: remove any meeting that overlaps with a not-available interval.
    vector<Interval> filtered = filterMeetings(meetings, notAvailable);

    // Now merge the remaining meeting intervals (if any overlap).
    vector<Interval> merged = mergeIntervals(filtered);

    // Output the final intervals.
    cout << "Meetings the person can attend (merged):" << endl;
    for (const auto &in : merged) {
        cout << "[" << in.start << ", " << in.end << "]" << endl;
    }

    return 0;
}