57. Insert Interval

Problem Statement

link: LeetCode.cn LeetCode

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example:

Input: intervals = [[1,3],[6,9]] Output: newInterval = [2,5]

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]] Output: newInterval = [4,8]

Solution Approach

The solution aims at navigating through the sorted intervals list, placing the new interval in the correct position, and merging any overlapping intervals.

Algorithm

1. Initialize Phase: Begin by iterating over the list, appending all intervals that come before the newInterval to the result.
2. Merge Phase: As we continue iterating, if we encounter overlapping intervals with the newInterval, merge them by adjusting the start and end of the newInterval.
3. Append Phase: Append the merged newInterval to the result, and then append the rest of the intervals in the original list that come after newInterval.

Implement

    class Solution:
      def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
          i = 0
          if not intervals:
              return [newInterval]
          n = len(intervals)
          res = []
          while i < n and newInterval[0] > intervals[i][1]:
              res. append(intervals[i])
              i += 1
          l, r = newInterval
          while i < n and r >= intervals[i][0]:
              l = min(l, intervals[i][0])
              r = max(r, intervals[i][1])
              i += 1
          res.append([l, r])
          res.extend(intervals[i:])
          return res
      

    
    

Twitter  facebook  Email