Are the ranges merging from top to bottom?

Question

I want to combine several such intervals:

>>> ranges = [(30, 45), (40, 50), (10, 50), (60, 90), (90, 100)] >>> merge(ranges) [(10, 50), (60, 100)] 

I'm not in the cs box. I know how to do this through iteration, but ask yourself if there is a more efficient top-down approach for merging them more efficiently, perhaps using some special data structure?

Thanks.

Answer 1

Yes, an effective way to do this is to use a tree.

Answer 2

The spanning tree definitely works, but it is more complex than what you need. The interval tree is an “online solution”, so it allows you to add some intervals, view the union, add additional intervals, view again, etc.

If you have all the intervals ahead, you can do something simpler:

• Start by typing

  range = [(30, 45), (40, 50), (10, 50)]

• Convert range list to endpoint list. If you have a range (A, B), you will convert it to two endpoints: (A, 0) will be the left endpoint and (B, 1) will be the right endpoint.

  endpoints = [(30, 0), (45, 1), (40, 0), (50, 1), (10, 0), (50, 1)]

• Endpoint sorting

  endpoints = [(10, 0), (30, 0), (40, 0), (45, 1), (50, 1), (50, 1)]

• Scan forward through the list of endpoints. Increase the counter when you see the left endpoint and decrease the counter when you see the right endpoint. Whenever the counter goes to 0, you close the current combined interval.

This solution can be implemented in several lines.

Answer 3

The following algorithm in C # does what you want. It uses DateTime interval intervals, but you can adjust it as you like. As soon as the collection is sorted in ascending order of the beginning, if the beginning of the next interval is at or to the end of the previous, they overlap, and you increase the end time, if necessary. Otherwise, they do not overlap, and you save the previous result.

 public static List<DateTimeRange> MergeTimeRanges(List<DateTimeRange> inputRanges) { List<DateTimeRange> mergedRanges = new List<DateTimeRange>(); // Sort in ascending start order. inputRanges.Sort(); DateTime currentStart = inputRanges[0].Start; DateTime currentEnd = inputRanges[0].End; for (int i = 1; i < inputRanges.Count; i++) { if (inputRanges[i].Start <= currentEnd) { if (inputRanges[i].End > currentEnd) { currentEnd = inputRanges[i].End; // Extend range. } } else { // Save current range to output. mergedRanges.Add(new DateTimeRange(currentStart, currentEnd)); currentStart = inputRanges[i].Start; currentEnd = inputRanges[i].End; } } mergedRanges.Add(new DateTimeRange(currentStart, currentEnd)); return mergedRanges; }