优化基于BFS的区间合并算法——大数据集性能提升需求

Let's break down why your current BFS approach struggles with large datasets and fix it step by step.

The Root Cause of Poor Performance #

Your implementation has a critical bottleneck: the inner loop that iterates through all n intervals every time you process an element from the queue. Even with a set for O(1) visited checks, this leads to an overall time complexity of O(n²) in the worst case (e.g., all intervals overlap with each other). This is why you're seeing such slowdowns with large datasets—your initial O(nlogn)+O(n) estimate doesn't account for this nested scan.

Optimization Strategies #

We have two paths forward: optimizing your BFS approach to match the efficiency of standard interval merging, or switching to the optimal linear approach after sorting.

Option 1: Optimized BFS (Preserving Your Core Approach)

The key fix is to sort intervals first—once sorted by their left endpoint, overlapping intervals will always be contiguous. This lets us avoid scanning the entire list every time, and instead only check subsequent intervals that could possibly overlap.

Here's the revised code:

import sys
from collections import deque

def merge_graph(intervals, visited, start_idx):
    q = deque()
    q.append(intervals[start_idx])
    visited.add(start_idx)
    start_lim = intervals[start_idx][0]
    end_lim = intervals[start_idx][1]
    
    # Use sorted order to only check relevant subsequent intervals
    j = start_idx + 1
    while q or j < len(intervals):
        if q:
            left, right = q.popleft()
            start_lim = min(start_lim, left)
            end_lim = max(end_lim, right)
        # Scan only intervals that could overlap with current merged range
        while j < len(intervals) and intervals[j][0] <= end_lim:
            if j not in visited:
                visited.add(j)
                q.append(intervals[j])
                end_lim = max(end_lim, intervals[j][1])
            j += 1
    return [start_lim, end_lim]

def merge_intervals(intervals):
    if not intervals:
        return []
    # Sort intervals by left endpoint (O(nlogn) time)
    intervals.sort()
    n = len(intervals)
    visited = set()
    merged_intervals = []
    for i in range(n):
        if i not in visited:
            merged_intervals.append(merge_graph(intervals, visited, i))
    return merged_intervals

Key Improvements:

• Sorting: Ensures overlapping intervals are contiguous, eliminating full list scans.
• Targeted Scanning: We only check intervals after the current start index, stopping once we hit an interval that can't overlap with our merged range.
• Early End Updates: We update end_lim immediately when adding a new interval to the queue, reducing redundant checks.

Option 2: Optimal Linear Merge (Fastest Approach)

If you're open to moving away from BFS, the standard interval merging algorithm is far more efficient—it runs in O(nlogn) time (from sorting) plus O(n) linear traversal, with minimal overhead.

Here's the implementation:

def merge_intervals_linear(intervals):
    if not intervals:
        return []
    # Sort by left endpoint
    intervals.sort()
    merged = [intervals[0]]
    for current in intervals[1:]:
        last_merged = merged[-1]
        # Check if current interval overlaps with the last merged interval
        if current[0] <= last_merged[1]:
            # Merge them by updating the right endpoint
            merged[-1] = [last_merged[0], max(last_merged[1], current[1])]
        else:
            # No overlap, add as a new interval
            merged.append(current)
    return merged

Why This Is Better:

• No queue or visited set overhead—uses constant extra space (excluding the result list).
• Each interval is processed exactly once, leading to consistent O(nlogn) performance even for large datasets.

Final Notes #

If you need to stick with BFS (e.g., for learning purposes), the optimized sorted BFS version will bring your performance in line with the standard approach. For production use, the linear merge is the clear choice—it's simpler, faster, and uses less memory.

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