fork(9) download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <utility>
  4. using namespace std;
  5.  
  6. // set<pair<int, int> > can also be used, but this way seems conceptually simpler
  7. map<int, pair<int, int> > intervals;
  8.  
  9. void insert(int left, int right)
  10. {
  11. 	if (!intervals.empty())
  12. 	{
  13. 		// get the next bigger element
  14. 		auto current = intervals.upper_bound(left);
  15. 		// checking if not found is not needed because of decrement and how C++ iterators work
  16. 		// decrement to get next smaller one instead, but only if we're not that the beginning
  17. 		if (current != intervals.begin())
  18. 			--current;
  19. 		// skip current if it's entirely to the left of the new interval
  20. 		if (current->second.second < left)
  21. 			++current;
  22. 		// update new starting point if there's an overlap and current is more to the left
  23. 		if (current != intervals.end() && current->first <= right)
  24. 			left = min(left, current->first);
  25. 		// iterate through while there's an overlap (deleting as we go)
  26. 		for (; current != intervals.end() && current->first <= right;
  27. 		       current = intervals.erase(current))
  28. 			// update the end point of new interval
  29. 			right = max(right, current->second.second);
  30. 	}
  31. 	// insert our pair
  32. 	intervals[left] = make_pair(left, right);
  33. }
  34.  
  35. int main() {
  36. 	insert(1,2);
  37. 	insert(4,8);
  38. 	insert(3,10);
  39. 	for (auto it: intervals)
  40. 	    cout << it.first << " " << it.second.second << endl;
  41. 	return 0;
  42. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2
3 10
https://ideone.com/B7tkGs
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!