#include #include #include 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 filterMeetings(const vector& meetings, const vector& notAvail) { vector 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 mergeIntervals(const vector& intervals) { if (intervals.empty()) return {}; vector 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 meetings = { {9, 10}, {9, 11}, {13, 14} }; // Not-available intervals vector 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 filtered = filterMeetings(meetings, notAvailable); // Now merge the remaining meeting intervals (if any overlap). vector 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; }