[Leetcode] 0057. Insert Interval

/ Leetcode, Technical Article / By

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

Table of contents

Medium

 

You are given an array of non-overlapping intervals intervals where intervals[i] = [start i , end i ] represent the start and the end of the i th interval and intervals is sorted in ascending order by start i. 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 start i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1:

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

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

  • 0 <= intervals.length <= 10 4
  • intervals[i].length == 2
  • 0 <= start i <= end i <= 10 5
  • intervals is sorted by start i in ascending order.
  • newInterval.length == 2
  • 0 <= start <= end <= 10 5

Python

				
					# time complexity: O(n) # space complexity: O(n) from typing import List class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List [int]]: result = [] i = 0 while i < len(intervals) and newInterval[0] > intervals[i][1]: result.append(intervals[i]) i += 1 while i < len (intervals) and newInterval[1] >= intervals[i][0]: newInterval[0] = min(intervals[i][0], newInterval[0]) newInterval[1] = max(intervals[i][ 1], newInterval[1]) i += 1 result.append(newInterval) while i < len(intervals): result.append(intervals[i]) i += 1 return result intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] newInterval = [4, 8] print(Solution().insert(intervals, newInterval))

related articles