fork(1) download
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <set>
  4. #include <tuple>
  5. #include <vector>
  6.  
  7. struct Interval
  8. {
  9. double start;
  10. double end;
  11. };
  12.  
  13. //-----------------------------------------------------------------------------
  14. // Enum to qualify event: Start/End of "segment-line"
  15. enum class EIntervalState
  16. {
  17. Start,
  18. End
  19. };
  20.  
  21. //-----------------------------------------------------------------------------
  22. // Events used for collision detection
  23. struct Event
  24. {
  25. double pos;
  26. EIntervalState state;
  27. std::size_t id;
  28. };
  29.  
  30. //-----------------------------------------------------------------------------
  31. // Comparator to use if {1, 2} and {2, 3} should overlap
  32. class LessIncludeLimit
  33. {
  34. public:
  35. bool operator()(const Event& lhs, const Event& rhs) const
  36. {
  37. return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state);
  38. }
  39. };
  40.  
  41. //-----------------------------------------------------------------------------
  42. // Comparator to use if {1, 2} and {2, 3} should not overlap
  43. class LessExcludeLimit
  44. {
  45. public:
  46. bool operator()(const Event& lhs, const Event& rhs) const
  47. {
  48. return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state);
  49. }
  50. };
  51.  
  52. //-----------------------------------------------------------------------------
  53. std::vector<Event> MakeEvents(const std::vector<Interval>& intervals)
  54. {
  55. std::vector<Event> res;
  56. std::size_t id = 0;
  57. for (const auto& interval : intervals)
  58. {
  59. res.push_back({interval.start, EIntervalState::Start, id});
  60. res.push_back({interval.end, EIntervalState::End, id});
  61. ++id;
  62. }
  63. return res;
  64. }
  65.  
  66. //-----------------------------------------------------------------------------
  67. template <typename Less>
  68. std::vector<std::pair<std::size_t, std::size_t>>
  69. ComputeOverlappingIntervals(std::vector<Event>&& events, Less less)
  70. {
  71. std::sort(events.begin(), events.end(), less);
  72.  
  73. std::set<std::size_t> activeIds;
  74. std::vector<std::pair<std::size_t, std::size_t>> res;
  75.  
  76. for (const auto& event : events)
  77. {
  78. switch (event.state)
  79. {
  80. case EIntervalState::Start:
  81. {
  82. for (const auto& id : activeIds)
  83. {
  84. res.emplace_back(std::minmax(event.id, id));
  85. }
  86. activeIds.emplace(event.id);
  87. break;
  88. }
  89. case EIntervalState::End:
  90. {
  91. activeIds.erase(event.id);
  92. break;
  93. }
  94. }
  95. }
  96. return res;
  97. }
  98.  
  99. //-----------------------------------------------------------------------------
  100. int main()
  101. {
  102. const std::vector<Interval> intervals = {
  103. {1, 3},
  104. {12, 14},
  105. {2, 4},
  106. {13, 15},
  107. {5, 10}
  108. };
  109.  
  110. for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals), LessExcludeLimit{})) {
  111. std::cout << "intervals " << p.first << " and " << p.second << " overlap\n";
  112. }
  113.  
  114. }
  115.  
Success #stdin #stdout 0s 15248KB
stdin
Standard input is empty
stdout
intervals 0 and 2 overlap
intervals 1 and 3 overlap