Buckets:
| tags: | |
| - intervals | |
| # Insert Interval [Link](https://neetcode.io/problems/insert-new-interval/question) | |
| You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [start_i, end_i]` represents the start and the end time of the `ith` interval. `intervals` is initially sorted in ascending order by `start_i`. | |
| You are given another interval `newInterval = [start, end]`. | |
| Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `start_i` and also `intervals` still does not have any overlapping intervals. You may merge the overlapping intervals if needed. | |
| Return `intervals` after adding `newInterval`. | |
| Note: Intervals are _non-overlapping_ if they have no common point. For example, [1,2] and [3,4] are non-overlapping, but [1,2] and [2,3] are overlapping. | |
| **Example 1:** | |
| ```java | |
| Input: intervals = [[1,3],[4,6]], newInterval = [2,5] | |
| Output: [[1,6]] | |
| ``` | |
| **Example 2:** | |
| ```java | |
| Input: intervals = [[1,2],[3,5],[9,10]], newInterval = [6,7] | |
| Output: [[1,2],[3,5],[6,7],[9,10]] | |
| ``` | |
| #### Solution | |
| Use binary search to find appropriate position where new interval can be inserted based on start time of the intervals. Loop over the intervals after inserting and adjust the end time of the interval. EDGE CASE: If intervals is empty, return `newInterval` inside list. | |
| ```python | |
| class Solution: | |
| def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: | |
| if not intervals: | |
| return [newInterval] | |
| res = [] | |
| left, right = 0, len(intervals) | |
| while left <= right: | |
| mid = (left + right) // 2 | |
| if interval[mid] < newInterval[0]: | |
| left += 1 | |
| else: | |
| right -= 1 | |
| intervals.insert(left, newInterval) | |
| for interval in intervals: | |
| if not res or res[-1][1] < interval[1]: | |
| res.append(interval) | |
| else: | |
| res[-1][1] = max(res[-1][1], interval[1]) | |
| return res | |
| ``` | |
| # Merge Intervals [Link](https://leetcode.com/problems/merge-intervals/) | |
| Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return _an array of the non-overlapping intervals that cover all the intervals in the input_. | |
| ```java | |
| Input: intervals = [[1,3],[2,6],[8,10],[15,18]] | |
| Output: [[1,6],[8,10],[15,18]] | |
| Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. | |
| Input: intervals = [[1,4],[4,5]] | |
| Output: [[1,5]] | |
| Explanation: Intervals [1,4] and [4,5] are considered overlapping. | |
| Input: intervals = [[4,7],[1,4]] | |
| Output: [[1,7]] | |
| Explanation: Intervals [1,4] and [4,7] are considered overlapping. | |
| ``` | |
| #### Solution: | |
| Sort the intervals based on start time, then merge them. | |
| ```python | |
| class Solution: | |
| def merge(self, intervals: List[List[int]]) -> List[List[int]]: | |
| intervals.sort(key=lambda x: x[0]) | |
| res = [intervals[0]] | |
| for start, end in intervals[1:]: | |
| if start <= res[-1][1]: | |
| res[-1][1] = max(res[-1][1], end) | |
| else: | |
| res.append([start, end]) | |
| return res | |
| ``` | |
| ##### Follow-up | |
| If the data is streaming, how can it be handled? applying sorting will increase the complexity. | |
| Using Tree in this case is more optimal: | |
| ```python unwrap:true | |
| from typing import List, Optional | |
| from collections import deque | |
| class IntervalNode: | |
| def __init__(self, start: int, end: int): | |
| self.start = start | |
| self.end = end | |
| self.left: Optional[IntervalNode] = None | |
| self.right: Optional[IntervalNode] = None | |
| self.max_end = end # For efficient overlap queries | |
| class StreamingIntervalMerger: | |
| def __init__(self): | |
| self.root: Optional[IntervalNode] = None | |
| def add_interval(self, start: int, end: int) -> None: | |
| """Add new interval and merge with overlaps in O(log n + k) time""" | |
| if start > end: | |
| return | |
| # Find all overlapping intervals | |
| overlaps = [] | |
| self._find_overlaps(self.root, start, end, overlaps) | |
| if not overlaps: | |
| # No overlaps, just insert | |
| self.root = self._insert(self.root, start, end) | |
| return | |
| # Compute merged bounds | |
| merged_start = min(start, min(node.start for node in overlaps)) | |
| merged_end = max(end, max(node.end for node in overlaps)) | |
| # Remove all overlapping intervals | |
| for node in overlaps: | |
| self.root = self._delete(self.root, node.start) | |
| # Insert merged interval | |
| self.root = self._insert(self.root, merged_start, merged_end) | |
| def get_merged_intervals(self) -> List[List[int]]: | |
| """Get all non-overlapping intervals in sorted order - O(n)""" | |
| result = [] | |
| self._inorder(self.root, result) | |
| return result | |
| def _insert(self, root: Optional[IntervalNode], start: int, end: int) -> Optional[IntervalNode]: | |
| if not root: | |
| return IntervalNode(start, end) | |
| if start < root.start: | |
| root.left = self._insert(root.left, start, end) | |
| else: | |
| root.right = self._insert(root.right, start, end) | |
| root.max_end = max(root.max_end, end) | |
| return root | |
| def _find_overlaps(self, node: Optional[IntervalNode], | |
| start: int, end: int, overlaps: List[IntervalNode]) -> None: | |
| if not node: | |
| return | |
| # Check current node for overlap | |
| if self._intervals_overlap(node.start, node.end, start, end): | |
| overlaps.append(node) | |
| # Traverse left if possible overlap exists | |
| if node.left and node.left.max_end >= start: | |
| self._find_overlaps(node.left, start, end, overlaps) | |
| # Traverse right | |
| self._find_overlaps(node.right, start, end, overlaps) | |
| def _intervals_overlap(self, a_start: int, a_end: int, b_start: int, b_end: int) -> bool: | |
| return a_start <= b_end and b_end >= a_start | |
| def _delete(self, root: Optional[IntervalNode], target_start: int) -> Optional[IntervalNode]: | |
| if not root: | |
| return root | |
| if target_start < root.start: | |
| root.left = self._delete(root.left, target_start) | |
| elif target_start > root.start: | |
| root.right = self._delete(root.right, target_start) | |
| else: | |
| # Found node to delete | |
| if not root.left: | |
| return root.right | |
| elif not root.right: | |
| return root.left | |
| # Node has two children, get inorder successor | |
| min_node = self._min_value_node(root.right) | |
| root.start = min_node.start | |
| root.end = min_node.end | |
| root.right = self._delete(root.right, min_node.start) | |
| if root: | |
| root.max_end = max((node.max_end for node in self._get_all_nodes(root))) | |
| return root | |
| def _min_value_node(self, node: IntervalNode) -> IntervalNode: | |
| current = node | |
| while current.left: | |
| current = current.left | |
| return current | |
| def _get_all_nodes(self, node: IntervalNode) -> List[IntervalNode]: | |
| result = [node] | |
| if node.left: | |
| result.extend(self._get_all_nodes(node.left)) | |
| if node.right: | |
| result.extend(self._get_all_nodes(node.right)) | |
| return result | |
| def _inorder(self, node: Optional[IntervalNode], result: List[List[int]]) -> None: | |
| if not node: | |
| return | |
| self._inorder(node.left, result) | |
| result.append([node.start, node.end]) | |
| self._inorder(node.right, result) | |
| ``` |
Xet Storage Details
- Size:
- 7.65 kB
- Xet hash:
- a8fe9bde2ef3d36ca01e8ebab4bb5af82193c899f2b88e148809b2c8e688f90c
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.