#include <iostream>
#include <vector>
#include <algorithm>
struct Interval {
int start;
int end;
};
// Returns how many intervals must be removed
int eraseMinimumOverlaps(std::vector<Interval>& intervals) {
if (intervals.empty())
return 0;
// Sort by end time
std::sort(intervals.begin(), intervals.end(),
[](const Interval& a, const Interval& b) {
return a.end < b.end;
});
int removed = 0;
int lastEnd = intervals[0].end;
for (size_t i = 1; i < intervals.size(); i++) {
if (intervals[i].start < lastEnd) {
// Overlap → remove this interval
removed++;
} else {
// No overlap → keep it
lastEnd = intervals[i].end;
}
}
return removed;
}
// Returns the intervals that remain after removing overlaps
std::vector<Interval> keepNonOverlapping(std::vector<Interval> intervals) {
if (intervals.empty())
return {};
std::sort(intervals.begin(), intervals.end(),
[](const Interval& a, const Interval& b) {
return a.end < b.end;
});
std::vector<Interval> result;
result.push_back(intervals[0]);
int lastEnd = intervals[0].end;
for (size_t i = 1; i < intervals.size(); i++) {
if (intervals[i].start >= lastEnd) {
result.push_back(intervals[i]);
lastEnd = intervals[i].end;
}
}
return result;
}
int main() {
// The only overlap is between [5,7] and [4,10]
// To keep the most intervals, we keep the one that ends earlier → [5,7]
std::vector<Interval> v = {{1,3}, {5,7}, {4,10}, {11,14}};
int removed = eraseMinimumOverlaps(v);
auto kept = keepNonOverlapping(v);
std::cout << "Removed: " << removed << "\nKept: ";
for (auto& x : kept)
std::cout << "[" << x.start << "," << x.end << "] ";
}
/*
run:
Removed: 1
Kept: [1,3] [5,7] [11,14]
*/
