How many event pairs overlap
A room-booking audit counts every pair of events that clash so the worst offenders can be resolved.
- Every event has a half-open interval [start, end).
- A pair overlaps when the two intervals share at least one point.
- Count each unordered pair once.
conflictPairs(events: list<Event>) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int conflictPairs(std::vector<Event> events) {
}Worked examples
| Call | Result |
|---|---|
conflictPairs(std::vector<Event>{Event{1, 5}, Event{3, 8}, Event{10, 15}}) | 1 |
conflictPairs(std::vector<Event>{Event{1, 5}, Event{6, 10}}) | 0 |
conflictPairs(std::vector<Event>{Event{1, 5}, Event{2, 4}, Event{3, 8}}) | 3 |
conflictPairs(std::vector<Event>{Event{1, 10}, Event{2, 3}, Event{4, 5}, Event{6, 7}}) | 3 |
Hint
A brute-force double loop over all i < j pairs and the overlap test from bookings-overlap.
Reference solution in C++
int conflictPairs(std::vector<Event> events) {
int count = 0;
for (size_t i = 0; i < events.size(); i++) {
for (size_t j = i + 1; j < events.size(); j++) {
if (events[i].start < events[j].end && events[j].start < events[i].end) count++;
}
}
return count;
}