Insert Interval — LeetCode 57 Python Solution
MediumArray
- Problem
- #57
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- intervals = [[1,3],[6,9]], newInterval = [2,5]
- Output
- [[1,5],[6,9]]
Python solution
Python
class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
def merge(intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
ans = [intervals[0]]
for s, e in intervals[1:]:
if ans[-1][1] < s:
ans.append([s, e])
else:
ans[-1][1] = max(ans[-1][1], e)
return ans
intervals.append(newInterval)
return merge(intervals)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(n) auxiliary |
Related problems
On study lists
This problem is on Blind 75, NeetCode 150, Grind 75 and Top Interview 150.
Frequently asked questions
- How hard is LeetCode 57. Insert Interval?
- LeetCode 57. Insert Interval is rated Medium on LeetCode.
- What is the time complexity of LeetCode 57. Insert Interval?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 57. Insert Interval?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 57. Insert Interval cover?
- LeetCode 57. Insert Interval is tagged Array on LeetCode.