求助：开发覆盖1到n的最少子区间算法，求伪代码与求解思路

Great question! The greedy algorithm is absolutely the right approach here—it's efficient and guarantees an optimal solution for this interval covering problem. Let me break down why it works, walk through the steps, and share pseudocode.

Why Greedy Works Here #

The problem has two key properties that make greedy applicable:

1. Greedy Choice Property: At each step, choosing the interval that extends our coverage the farthest (while starting within our current covered range) leads to the globally optimal solution. This is because maximizing the coverage per interval minimizes how many we need to use.
2. Optimal Substructure: Once we select an interval that extends our coverage to X, the problem reduces to covering from X+1 to n—and the optimal solution to the original problem includes the optimal solution to this subproblem.

Step-by-Step Algorithm #

Here's the core logic:

1. Sort Intervals: First, sort the intervals by their starting value in ascending order. If two intervals have the same start, sort them by their ending value in descending order (so we prioritize longer intervals when starts overlap).
2. Track Coverage: Iterate through the sorted intervals, keeping track of:
   • current_end: The farthest point we've successfully covered so far.
   • next_end: The farthest point we can reach by selecting the best possible interval in the current step.
   • count: The number of intervals we've used.
3. Expand Coverage: For each iteration, find all intervals that start within or immediately after our current coverage (i.e., start ≤ current_end + 1). Among these, pick the one that extends coverage the farthest. If no such interval exists (meaning there's a gap), return -1 (impossible to cover the range).
4. Repeat: Continue until we've covered up to n, then return the count of intervals used.

Pseudocode #

Function minIntervals(intervals, target_n):
    # Sort intervals by start ascending, then end descending
    sort intervals by their start value; if starts are equal, sort by end in reverse order
    
    current_coverage_end = 0
    interval_count = 0
    index = 0
    total_intervals = length of intervals
    
    while current_coverage_end < target_n:
        next_possible_end = current_coverage_end
        
        # Find the farthest we can reach from current coverage
        while index < total_intervals and intervals[index].start <= current_coverage_end + 1:
            next_possible_end = max(next_possible_end, intervals[index].end)
            index += 1
        
        # If we can't extend coverage, there's a gap—return -1
        if next_possible_end == current_coverage_end:
            return -1
        
        # Update coverage and increment count
        interval_count += 1
        current_coverage_end = next_possible_end
    
    return interval_count

Example Walkthrough #

Let's test this with your sample input:

• Intervals: [{1,2}, {1,3}, {2,3}], target_n=3
• Sorted intervals: [{1,3}, {1,2}, {2,3}]

1. Initial state: current_coverage_end=0, interval_count=0, index=0
2. First iteration:
   • Check intervals where start ≤ 0+1=1:
     • {1,3}: update next_possible_end to 3, index becomes 1
     • {1,2}: next_possible_end stays 3, index becomes2
     • {2,3}: start=2 >1, stop inner loop
   • next_possible_end=3 > current_coverage_end=0: increment count to1, set current_coverage_end=3
3. Loop ends (3 ≥3), return count=1. Perfect match for your expected result!

Edge Cases to Consider #

• Impossible Coverage: If there's a gap between intervals (e.g., intervals [{1,2}, {4,5}], n=5), the algorithm returns -1 because it can't bridge the gap between 2 and4.
• Single Interval: If one interval covers the entire range (e.g., [{1,5}], n=5), returns 1.
• Non-overlapping but contiguous: Intervals [{1,2}, {2,3}, {3,4}], n=4 returns3 (no way to do better).

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