如何用Python从区间集合中提取正确的非重叠独特区间？

The core issue with your current code is that it uses a complex, sequential interval comparison logic that doesn't accurately track how many input intervals cover each segment. The correct approach is to identify segments of the number line that are covered by exactly one input interval—these are your "non-overlapping unique intervals."

Correct Approach #

Here's a step-by-step breakdown of the right way to solve this:

1. Collect all critical points: Extract every start and end value from your input intervals. These points divide the number line into segments where coverage count is constant.
2. Sort and deduplicate: Sort these points and remove duplicates to get a clean list of segment boundaries.
3. Check coverage for each segment: For each segment between consecutive critical points, count how many input intervals include any point in that segment. If the count is exactly 1, add the segment to your result.

Fixed Code #

gene_bounds_list = [[1,10],[5,20], [6,21],[17,25],[22,23], [24,50],[30,55],[60,70]]

# Step 1: Collect all critical points (start and end of each interval)
points = []
for interval in gene_bounds_list:
    points.append(interval[0])
    points.append(interval[1])

# Step 2: Sort and deduplicate the points
sorted_points = sorted(list(set(points)))

result = []

# Step3: Check coverage for each segment between consecutive points
for i in range(len(sorted_points) - 1):
    a = sorted_points[i]
    b = sorted_points[i+1]
    
    # Skip zero-length segments
    if a == b:
        continue
    
    # Pick a midpoint to check coverage (avoids edge cases at interval boundaries)
    mid = (a + b) / 2
    coverage_count = 0
    
    for s, e in gene_bounds_list:
        if s <= mid <= e:
            coverage_count += 1
    
    # Add segment if it's covered by exactly one interval
    if coverage_count == 1:
        result.append([a, b])

print(result)

Output #

Running this code gives exactly your expected result:

[[1, 5], [21, 22], [23, 24], [25, 30], [50, 55], [60, 70]]

Why Your Original Code Failed #

Your original logic tried to modify intervals on the fly as you iterated through the list, but it didn't account for all overlapping scenarios (like multiple intervals covering the same segment). This led to including segments that were actually covered by multiple intervals (e.g., [6,10] which is covered by three input intervals).

The approach above avoids these pitfalls by breaking the problem into small, manageable segments where coverage is unambiguous.

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