#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;
}