I would use a naive approach first, using a side-table; it will be close to a sweeping line algorithm.
The idea:
- iterate through the connections in order (ordered by start time here)
- keeping a set of the currently involved connections
The trick is to keep track of the connections efficiently, and especially of when to remove them; a priority-queue is great for this.
Some help:
struct Connection {
uint32_t start;
uint32_t end;
}; // struct Connection
// WATCH OUT:
// std::priority_queue only let you access the MAXIMUM element, so the predicate
// is the OPPOSITE of what we usually write...
struct OrderByEnd {
bool operator()(Connection const& left, Connection const& right) const {
if (left.end > right.end) { return true; }
if (left.end < right.end) { return false; }
return left.start > right.start;
}
}; // struct OrderByEnd
using CurrentlyOverlappingType = std::priority_queue<Connection, std::deque<Connection>, OrderByEnd>;
And then, we sweep:
size_t countMaxNumberOfOverlaps(std::map<uint32_t, uint32_t> const& connections) {
if (connections.empty()) { return 0; }
size_t max = 0;
CurrentlyOverlappingType currentlyOverlapping;
for (auto const& con: connections) {
// Purge no longer overlapping connections
while (not currentlyOverlapping.empty() and currentlyOverlapping.top().end < con.first) {
currentlyOverlapping.pop();
}
// Debug:
if (not currentlyOverlapping.empty()) {
std::cout << "[" << con.first << ", " << con.second <<
"] is overlapping with: " << currentlyOverlapping.size() << " connections\n";
}
// The current connection is necessarily overlapping with itself
currentlyOverlapping.push(Connection{con.first, con.second});
max = std::max(max, currentlyOverlapping.size());
}
return max;
} // countMaxNumberOfOverlaps
And it works as expected:
[120, 200] is overlapping with: 1 connections
[250, 400] is overlapping with: 1 connections
[600, 800] is overlapping with: 1 connections
Max number of overlaps: 2
The complexity is harder to fathom. You have to sweep through the whole set of connections, but at each step the amount of work is proportional to the current number of overlapping connections...
- Worst case complexity: O(N * log(N)) I would say (because inserting in the priority queue is logarithmic)
- Average case complexity: O(N * log(O)) where O is the number of overlapping connections
Note: in the algorithmic analysis, I considered that the complexity of the purge part is amortized constant; we know items are going to be purged, so we can account for their purge in the cost of their insertion. N items are inserted, N items are going to be purged. The number of comparisons executed as part of the purge process is (I think) also amortized constant (the total for all items being bounded by a maximum of 2N) although it's intuition and not computation. And therefore, the cost of the purge is dwarfed by the cost of inserting the items in the priority queue, which log(O) per item.