MiddleCodeOccasionalNot answered yet
Return all meetings that overlap at least one other meeting
Given a list of meetings with half-open intervals [from, to), return the set of meetings that overlap at least one other meeting. Improve on the naive O(n^2) all-pairs check.
Requirements:
- Two meetings overlap iff their half-open intervals intersect.
- Target O(n log n) time.
struct Meeting { long from, to; };
std::vector<Meeting> crossing(std::vector<Meeting> meetings) {
// your code here
}Write the implementation.
Sort by from, then sweep tracking the running maximum to of all earlier-starting meetings. A meeting overlaps an earlier one when its from < maxEnd; when so, mark both it and the meeting that set maxEnd. Use a flag per meeting so each is reported once. O(n log n).
- ✗Comparing only adjacent sorted intervals, missing a meeting overlapped by an earlier non-adjacent one
- ✗Mixing closed and half-open boundary tests, so touching intervals are wrongly counted as overlapping
- ✗Reporting a meeting twice when it overlaps several others
- →How does the half-open
[from, to)rule change the boundary comparison? - →How does this differ from finding the maximum number of overlapping meetings?
Contents
Task
Return all meetings that overlap at least one other; faster than the naive O(n^2).
Solution
#include <vector>
#include <algorithm>
struct Meeting { long from, to; };
std::vector<Meeting> crossing(std::vector<Meeting> meetings) {
size_t n = meetings.size();
std::vector<size_t> idx(n);
for (size_t i = 0; i < n; ++i) idx[i] = i;
std::sort(idx.begin(), idx.end(),
[&](size_t a, size_t b){ return meetings[a].from < meetings[b].from; });
std::vector<bool> hit(n, false);
long maxEnd = -1; size_t maxIdx = 0;
for (size_t k = 0; k < n; ++k) {
size_t i = idx[k];
if (k > 0 && meetings[i].from < maxEnd) { // half-open: < the end
hit[i] = true; hit[maxIdx] = true;
}
if (meetings[i].to > maxEnd) { maxEnd = meetings[i].to; maxIdx = i; }
}
std::vector<Meeting> res;
for (size_t i = 0; i < n; ++i) if (hit[i]) res.push_back(meetings[i]);
return res;
}Key points
- Sort by start plus a running maximum end catches non-adjacent overlaps too.
- Half-open
[from, to): touching boundaries is not an overlap. - A per-meeting flag guarantees one report per meeting.
Contents
