Merge Intervals

Problem Id: 56 Difficulty: Medium Tag: Array Tag: Sort


Intuition

This could be solved using Greedy. We should first sort the arrays by the start value. Then, we go through the values one by one and merge necessary neighbours.

Solution


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort()
        start, end = intervals[0]
        ans = []
        for i, j in intervals:
            if i > end:
                ans.append([start, end])
                start, end = i, j
            else:
                end = max(end, j)
        ans.append([start, end])
        return ans