fork download 
  1. #include <deque>
  2. #include <iostream>
  3. #include <map>
  4. #include <queue>
  5.  
  6. struct Connection {
  7. 	uint32_t start;
  8. 	uint32_t end;
  9. }; // struct Connection
  10.  
  11. struct OrderByEnd {
  12. 	bool operator()(Connection const& left, Connection const& right) const {
  13. 		if (left.end > right.end) { return true; }
  14. 		if (left.end < right.end) { return false; }
  15. 		return left.start > right.start;
  16. 	}
  17. }; // struct OrderByEnd
  18.  
  19. using CurrentlyOverlappingType = std::priority_queue<Connection, std::deque<Connection>, OrderByEnd>;
  20.  
  21. size_t countMaxNumberOfOverlaps(std::map<uint32_t, uint32_t> const& connections) {
  22. 	if (connections.empty()) { return 0; }
  23.  
  24. 	size_t max = 0;
  25. 	CurrentlyOverlappingType currentlyOverlapping;
  26.  
  27. 	for (auto const& con: connections) {
  28. 		// Purge no longer overlapping connections
  29. 		while (not currentlyOverlapping.empty() and currentlyOverlapping.top().end < con.first) {
  30. 			currentlyOverlapping.pop();
  31. 		}
  32.  
  33. 		// Debug:
  34. 		if (not currentlyOverlapping.empty()) {
  35. 			std::cout << "[" << con.first << ", " << con.second <<
  36. 			    "] is overlapping with: " << currentlyOverlapping.size() << " connections\n";
  37. 		}
  38.  
  39. 		// The current connection is necessarily overlapping with itself
  40. 		currentlyOverlapping.push(Connection{con.first, con.second});
  41.  
  42. 		max = std::max(max, currentlyOverlapping.size());
  43. 	}
  44.  
  45. 	return max;
  46. } // countMaxNumberOfOverlaps
  47.  
  48. int main() {
  49. 	std::map<uint32_t, uint32_t> const connections = { { 100, 1000 },
  50. 	                                                   { 120,  200 },
  51. 	                                                   { 250,  400 },
  52. 	                                                   { 600,  800 } };
  53.  
  54.     size_t const max = countMaxNumberOfOverlaps(connections);
  55.  
  56.     std::cout << "Max number of overlaps: " << max << "\n";
  57. 	return 0;
  58. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin 
Standard input is empty
stdout 
[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
https://ideone.com/ypCaT0
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!