< Back




57. Insert Interval

We're asked to insert an interval into a list of already sorted intervals. Well, if the input is
sorted we're likely to use binary search to find the insert location. Once we do that, we use the
list .insert() method to insert the new interval. Finally, we merge the intervals just like
56. Merge Intervals.

The solution is as follows:


  class Solution:
      def insert(
          self, intervals: List[List[int]], newInterval: List[int]
      ) -> List[List[int]]:
          if not intervals:
              return [newInterval]

          newStart, newEnd = newInterval
          l, r, ans = 0, len(intervals) - 1, []

          while l <= r:
              m = (l + r) // 2

              if intervals[m][0] < newStart:
                  l = m + 1
              else:
                  r = m - 1

          intervals.insert(l, newInterval)

          for start, end in intervals:
              if not ans or ans[-1][1] < start:
                  ans.append([start, end])
              else:
                  ans[-1][1] = max(ans[-1][1], end)

          return ans


_ Time Complexity:

  O(n) - We process all intervals when we merge them and the new interval.

_ Space Complexity:

  O(n) - We store the new, merged interval list in ans.