Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Merge intervals

Sharing is caring!

Problem statement
Given a collection of intervals, merge all overlapping intervals.

Sample Input

[1,3],[2,6],[8,10],[15,18]

Output

[1,6],[8,10],[15,18]

Solution Concept
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.

  1. Sort all intervals in decreasing order of start time.
  2. 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.

Solution

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()

Notebook file
https://github.com/lucaslouca/coding-problems/tree/master/python/MergeIntervals