DenCT/test-storage / DSA Notes /Intervals.md
DenCT's picture
|
download
raw
7.65 kB
metadata
tags:
  - intervals

Insert Interval Link

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:

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

Output: [[1,6]]

Example 2:

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.

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

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.

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.

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:

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.