[Leetcode] 0057. Insert Interval

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

内容目录

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 ⁴
intervals[i].length == 2
0 <= start _i <= end _i <= 10 ⁵
intervals is sorted by start _i in ascending order.
newInterval.length == 2
0 <= start <= end <= 10 ⁵

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))

Medium

Python

相关文章