带时间上界的区间合并问题：能否优化O(nLogn)时间复杂度？

Great question! The standard interval merging approach relies on sorting intervals first (O(n log n) time) followed by a linear scan to merge overlaps—but when we know there's a fixed upper bound C on all interval start and end times, we can absolutely optimize this to a faster, linear-time (relative to n and C) solution.

The Core Idea: Difference Array + Prefix Sum #

Instead of sorting, we can use a difference array to track the "start" and "end" of interval coverage, then compute a prefix sum to identify continuous covered ranges. Here's how it works step by step:

1. Initialize a difference array

   • Create an array diff of size C + 2 (we add an extra slot to avoid index out-of-bounds when handling intervals ending exactly at C). Initialize all values to 0.
   • For each interval [s, e]:
     • Increment diff[s] by 1 (marks the start of a covered interval)
     • Decrement diff[e + 1] by 1 (marks the end of coverage, one position past the interval's end)

2. Compute prefix sum and merge intervals

   • Iterate through the diff array to calculate the running prefix sum, which tells us how many intervals cover the current position.
   • As we go, track when we enter a covered range (prefix sum goes from 0 to >0) and when we exit it (prefix sum drops back to 0). These entry/exit points become our merged intervals.

Time & Space Complexity #

• Time: O(n + C). We process all n intervals in linear time, then scan the C-sized array once. If C is significantly smaller than n log n (e.g., n=1e5, C=1e3), this is way faster than the standard O(n log n) sort-based approach.
• Space: O(C). This is the trade-off—if C is extremely large (e.g., C=1e9), this method is impossible due to memory constraints, and you're better off sticking with the standard sorting approach.

Example Walkthrough #

Let's say C=10, and our intervals are [[1,3], [2,6], [8,10]]:

1. Initialize diff as [0,0,0,0,0,0,0,0,0,0,0,0] (size 12 = 10+2)
2. Update for each interval:
   • [1,3]: diff[1] +=1 → diff[1] =1; diff[4] -=1 → diff[4] =-1
   • [2,6]: diff[2] +=1 → diff[2] =1; diff[7] -=1 → diff[7] =-1
   • [8,10]: diff[8] +=1 → diff[8] =1; diff[11] -=1 → diff[11] =-1
3. Compute prefix sum:
   • Pos 0: 0; Pos1:1; Pos2:2; Pos3:2; Pos4:1; Pos5:1; Pos6:1; Pos7:0; Pos8:1; Pos9:1; Pos10:1; Pos11:0
4. Merge covered ranges:
   • Start at pos1 (sum>0), end at pos6 (sum drops to 0 at pos7) → [1,6]
   • Start at pos8 (sum>0), end at pos10 (sum drops to 0 at pos11) → [8,10]

Key Notes #

• Make sure to handle edge cases: intervals that start/end exactly at C, empty input lists, or non-overlapping intervals (the method still works seamlessly).
• This approach only works if C is a manageable size—if C is larger than n log n, the standard sort-based method is more efficient in both time and space.

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