#include <deque>
#include <iostream>
#include <map>
#include <queue>

struct Connection {
	uint32_t start;
	uint32_t end;
}; // struct Connection

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>;

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

int main() {
	std::map<uint32_t, uint32_t> const connections = { { 100, 1000 },
	                                                   { 120,  200 },
	                                                   { 250,  400 },
	                                                   { 600,  800 } };
	                                                   
    size_t const max = countMaxNumberOfOverlaps(connections);
    
    std::cout << "Max number of overlaps: " << max << "\n";
	return 0;
}