DEV Community

Gangbaolede Li
Gangbaolede Li

Posted on

Leetcode 56: Merge Intervals

Problem statement:
https://leetcode.com/problems/merge-intervals/

  • Straight forward solution is to sort the intervals by start time, iterate them and check if two intervals overlap. If they overlap we take the union of those intervals; Otherwise, we take both of them.

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # sort intervals by start time
        intervals.sort(key=lambda i: i[0])

        res = []
        res.append(intervals[0])
        n = len(intervals)
        for i in range(1, n):
            if res[-1][1] >= intervals[i][0]:
                res[-1][1] = max(res[-1][1], intervals[i][1])
            else:
                res.append(intervals[i])
        return res
Enter fullscreen mode Exit fullscreen mode

Discussion (0)