Python动态维护非重叠整数区间集合的最优实现方案咨询

Hey there! Let's break down how to build this dynamic integer interval set in Python—you need it to handle merging overlapping ranges, splitting existing ones, checking membership, and iterating through all values, right? I'll walk you through an optimal implementation, including leveraging Python's built-in tools where possible.

Core Approach #

The key to efficiency here is maintaining a sorted, non-overlapping list of intervals. This lets us use binary search (via Python's bisect module) to quickly locate intervals that need merging or splitting, instead of scanning every interval every time. All operations (add, remove, membership check) will build on this ordered structure.

Implementation #

Here's a complete IntervalSet class that meets all your requirements:

import bisect
from typing import List, Tuple, Iterator

class IntervalSet:
    def __init__(self, intervals: List[Tuple[int, int]] = None):
        # Initialize with merged, non-overlapping intervals
        self.intervals = []
        if intervals:
            for start, end in intervals:
                self.add_interval(start, end)
    
    def add_interval(self, start: int, end: int) -> None:
        # Ensure start <= end (handle reversed input)
        if start > end:
            start, end = end, start
        
        # Find all intervals that overlap or are adjacent to the new interval
        merge_indices = []
        # Use bisect to find the first interval that starts after our new end
        idx = bisect.bisect_right(self.intervals, (end, float('inf')))
        
        # Backtrack to find all overlapping/adjacent intervals
        while idx > 0:
            idx -= 1
            curr_start, curr_end = self.intervals[idx]
            if curr_end < start - 1:  # No overlap or adjacency—stop searching
                break
            merge_indices.append(idx)
        
        # Merge the intervals if needed
        if merge_indices:
            new_start = min(start, self.intervals[merge_indices[0]][0])
            new_end = max(end, self.intervals[merge_indices[-1]][1])
            # Remove old intervals in reverse order to avoid index shifting issues
            for i in reversed(merge_indices):
                del self.intervals[i]
            # Insert the merged interval back into the sorted list
            bisect.insort(self.intervals, (new_start, new_end))
        else:
            # No overlaps—just insert the new interval in sorted position
            bisect.insort(self.intervals, (start, end))
    
    def remove_interval(self, start: int, end: int) -> None:
        if start > end:
            start, end = end, start
        
        remove_indices = []
        split_parts = []
        # Find the first interval that might overlap with our target range
        idx = bisect.bisect_left(self.intervals, (start, -float('inf')))
        # Check the previous interval in case it overlaps
        if idx > 0:
            prev_start, prev_end = self.intervals[idx-1]
            if prev_end >= start:
                idx -= 1
        
        # Iterate through all overlapping intervals
        while idx < len(self.intervals):
            curr_start, curr_end = self.intervals[idx]
            if curr_start > end:
                break  # No more overlapping intervals
            remove_indices.append(idx)
            # Split the current interval if parts fall outside the removal range
            if curr_start < start:
                split_parts.append((curr_start, start - 1))
            if curr_end > end:
                split_parts.append((end + 1, curr_end))
            idx += 1
        
        # Remove the old overlapping intervals
        for i in reversed(remove_indices):
            del self.intervals[i]
        # Add back the split parts (if any)
        for part in split_parts:
            bisect.insort(self.intervals, part)
    
    def __contains__(self, value: int) -> bool:
        # Use bisect to quickly find the interval that could contain the value
        idx = bisect.bisect_right(self.intervals, (value, float('inf'))) - 1
        if idx >= 0:
            curr_start, curr_end = self.intervals[idx]
            return curr_start <= value <= curr_end
        return False
    
    def __iter__(self) -> Iterator[int]:
        # Generator to iterate through all integers in the set (memory-efficient)
        for start, end in self.intervals:
            yield from range(start, end + 1)
    
    def __repr__(self) -> str:
        # Human-readable string representation of the interval set
        return ' '.join([f"{s} - {e}" for s, e in self.intervals])

Testing the Solution #

Let's verify it works with your example scenarios:

# Initialize with your starting intervals
interval_set = IntervalSet([(200, 400), (450, 470), (700, 900)])
print("Initial set:", interval_set)
# Output: Initial set: 200 - 400 450 - 470 700 - 900

# Add the overlapping interval 460-490
interval_set.add_interval(460, 490)
print("After adding 460-490:", interval_set)
# Output: After adding 460-490: 200 - 400 450 - 490 700 - 900

# Remove the interval 300-350
interval_set.remove_interval(300, 350)
print("After removing 300-350:", interval_set)
# Output: After removing 300-350: 200 - 300 350 - 400 450 - 490 700 - 900

# Check membership
print(320 in interval_set)  # False
print(360 in interval_set)  # True
print(480 in interval_set)  # True

# Iterate through the first 10 values
print("First 10 values:", list(iter(interval_set))[:10])
# Output: First 10 values: [200, 201, 202, 203, 204, 205, 206, 207, 208, 209]

Key Optimizations & Built-in Tools #

• bisect module: This built-in library lets us perform binary search on the sorted interval list, cutting down the time complexity of locating intervals from O(n) to O(log n). Critical for performance with large numbers of intervals.
• Generator iteration: Using yield from in __iter__ avoids creating a massive list of integers (especially useful for large ranges like 1-1,000,000), keeping memory usage low.
• Pythonic interface: Implementing __contains__ lets you use the natural value in interval_set syntax, and __repr__ provides clean debug output.

Notes on Edge Cases #

• Handles reversed input (e.g., adding 490-460 works the same as 460-490).
• Correctly splits intervals when removing a range that overlaps multiple existing intervals.
• Properly merges adjacent intervals (e.g., adding 400-450 to the initial set would merge 200-400 and 450-470 into 200-470).

内容的提问来源于stack exchange，提问作者user8472