Given a collection of intervals, merge all overlapping intervals.
We sort the intervals by decreasing order of start times. That way we can quickly check if intervals overlap or not by comparing start time of previous interval with end time of current interval.
- Sort all intervals in decreasing order of start time.
- Traverse sorted intervals starting from first interval, do following for every interval:
- If current interval is not first interval and it overlaps with previous interval, then merge it with previous interval. Keep doing it while the interval overlaps with the previous one.
- Else add current interval to output list of intervals.
import sys class Interval: def __init__(self, start, end): self.start = start self.end = end def __eq__(self, other): return self.start == other.start def __lt__(self, other): return self.start < other.start def __repr__(self): return "[%s, %s]" % (self.start, self.end) def merge(intervals): # Sort all intervals in decreasing order of start time. intervals.sort(reverse=True) n = len(intervals) cursor = 0 for i in range(0, n): if (cursor != 0 and intervals[i].end >= intervals[cursor-1].start): while (cursor != 0 and intervals[i].end >= intervals[cursor-1].start): # While current interval overlaps with previous interval --> Merge intervals[cursor-1].start = min(intervals[cursor-1].start, intervals[i].start) intervals[cursor-1].end = max(intervals[cursor-1].end, intervals[i].end) cursor -= 1 else: intervals[cursor] = intervals[i] cursor += 1 return intervals[:cursor] def main(): intervals = [Interval(8,10),Interval(1,3),Interval(2,6),Interval(15,18)] print("Input: %s" % (intervals)) print("Output: %s" % merge(intervals)) main()