56. Merge Intervals

Problem Statement

link: https://leetcode.com/problems/merge-intervals/ https://leetcode.cn/problems/merge-intervals/

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]

Input: intervals = [[1,4],[4,5]] Output: [[1,5]]

Solution Approach

The key idea is to first sort the intervals by their starting points and then merge overlapping intervals in a single pass.

Algorithm

1. Sort Intervals: Sort by starting points using the lambda function.
2. Initialize: Create an empty new_interval list for merged intervals.
3. Merge Overlaps: Traverse sorted intervals. If no overlap with the last in new_interval, append; if overlap, merge by updating the end point.

Implement

    class Solution:
      def merge(self, intervals: List[List[int]]) -> List[List[int]]:
          intervals.sort(key = lambda x: x[0]) # sort with lambda
          new_interval = []
          l = len(intervals)
          for i in range(l):
              if not new_interval or new_interval[-1][1] < intervals[i][0]:
                  new_interval.append(intervals[i])
              else:
                  new_interval[-1][1] = max(new_interval[-1][1],intervals[i][1]) # add max here
          return new_interval

    
    

Twitter  facebook  Email