寻找最长重叠区间对：基于递归的次O(n²)解法问询

Alright, let's work through this problem together. You need a recursive, non-DP approach that runs in o(n²) time to find the pair of intervals with the longest overlap—here's a divide-and-conquer solution that checks all those boxes:

The core idea is to split the problem into smaller subproblems, solve them recursively, then combine the results. This fits your recursion requirement and hits the o(n²) time target.

Step 1: Recursive Pre-Sort #

First, we sort all intervals by their start value a. If two intervals have the same start, sort them by their end value b in descending order. We can use a recursive sorting algorithm like merge sort here to keep the entire solution rooted in recursion. This step runs in O(n log n) time.

Step 2: Recursive Divide-and-Conquer Process #

We split the sorted interval array into left and right subarrays, then:

1. Recursively find the maximum overlap pair in the left subarray
2. Recursively find the maximum overlap pair in the right subarray
3. Find the maximum overlap pair that crosses the left and right subarrays
4. Return the pair with the longest overlap from the three results

Key: Efficiently Finding Cross-Subarray Overlaps #

Since the array is sorted, every interval in the left subarray has a start ≤ every interval in the right subarray. For a right interval [a_r, b_r], its overlap with a left interval [a_l, b_l] is min(b_l, b_r) - a_r + 1 (if b_l ≥ a_r; otherwise, no overlap).

To maximize this value quickly:

• When we process each subarray recursively, we'll also return a list of the subarray's interval end values b (paired with their original intervals), sorted in descending order.
• For each right interval, we use a recursive binary search on the left's descending b list to find the largest b_l that's ≥ a_r. This lets us compute the maximum possible overlap for that right interval in O(log n) time.

Step 3: Recursive Function Breakdown #

Here's a concrete breakdown of the recursive function max_overlap(intervals):

• Base Case: If the array has 0 or 1 interval, return an empty pair (overlap length 0) and a descending list of (end value, interval) tuples (empty or containing the single interval's data).
• Split: Divide the interval array into left and right halves.
• Recurse: Call max_overlap on both halves, getting their best overlap pairs, maximum lengths, and descending (end value, interval) lists.
• Check Cross Pairs: For each interval in the right half, use recursive binary search on the left's list to find the best possible left interval overlap. Track the maximum cross-subarray overlap pair.
• Merge Results: Compare the best left, right, and cross pairs. Pick the one with the longest overlap.
• Merge End Value Lists: Recursively merge the left and right descending (end value, interval) lists into a single sorted descending list to return with the result.

Time Complexity Breakdown #

• Sorting: O(n log n) (recursive merge sort)
• Divide-and-Conquer: The recurrence relation is T(n) = 2T(n/2) + O(n log n). By the Master Theorem, this resolves to O(n (log n)²), which is definitely o(n²) (since n² grows much faster than n*(log n)²).

Example Walkthrough #

Take your sample intervals [3,6] and [5,9]:

1. Sorted array is [[3,6], [5,9]]
2. Split into left [[3,6]] and right [[5,9]]
3. Left recursion returns no pair, length 0, end list [(6, [3,6])]
4. Right recursion returns no pair, length 0, end list [(9, [5,9])]
5. Cross pair check: For [5,9], binary search finds 6 ≥ 5. Overlap length is min(6,9) -5 +1 = 2
6. The cross pair is the best, so we return ([3,6], [5,9]) with length 2

内容的提问来源于stack exchange，提问作者Andrej Kováč