DenCT/test-storage / DSA Notes /Intervals.md
DenCT's picture
|
download
raw
7.65 kB
---
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.