Interval Covering

Interval covering chooses the fewest available intervals whose union covers a target range. The greedy rule is to take, among intervals that can extend the already covered prefix, the one reaching farthest right. Choosing the longest interval overall or the earliest finishing one answers the wrong question. A sorted scan makes eligibility and impossible gaps explicit.

Prerequisites: Interval sorting; stays-ahead proofs.

Build the idea

1. Represent progress

   The target is the half-open interval [L,R), with L≤R. An empty target L=R needs zero intervals. covered means every target position from L up to covered is already covered. Sort candidate intervals by left endpoint. An interval with left≤covered is eligible to continue without a gap, but it helps only if right>covered.

2. Scan all eligible candidates

   At each step, consume every newly eligible interval and retain the one with greatest right endpoint. If no interval improves covered, there is a gap and the answer is IMPOSSIBLE. Otherwise record its original ID and advance covered. Scanned intervals not chosen can be discarded: they end no farther than the chosen interval, so cannot improve any later frontier.

   $$\mathrm{nextFrontier}=\max \{\mathrm{right}:\mathrm{left}\le \mathrm{covered}\}$$

3. Correctness proof: stay ahead by number of choices

   After one choice, greedy reaches at least as far as any feasible first interval. Inductively suppose its k-choice frontier dominates another cover’s k-choice frontier. That other cover’s next interval begins before its own frontier, hence is also eligible by the greedy frontier; greedy’s next extension reaches at least as far. If greedy cannot advance, no competing cover can cross the gap. Therefore no cover reaches R in fewer choices.

4. Trace the sample

   Target [0,10) has intervals [−1,3),[0,5),[3,7),[5,10),[7,12). Initially the first two are eligible and [0,5) wins. At frontier 5, [3,7) and [5,10) are eligible; choose [5,10). Two intervals finish the job. The longer-reaching [7,12) was not initially eligible, so selecting it first would leave a gap.

5. Recognize assumptions

   We cover a continuous range, not merely a list of required points. The objective is the number of chosen intervals with equal cost. Arbitrary interval costs turn it into a different optimization, often requiring DP or shortest paths. The scan assumes each candidate is already given with left≤right and that endpoint touching is sufficient to continue coverage.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Interval{
    long long l,r;
    int id;
};
int main(){
    int n;
    long long left,right;
    std::cin>>n>>left>>right;
    std::vector<Interval>a(n);
    for(int i=0;i<n;++i){
        std::cin>>a[i].l>>a[i].r;
        a[i].id=i+1;
    }
    std::sort(a.begin(),a.end(),[](Interval x,Interval y){
        return x.l!=y.l?x.l<y.l:x.id<y.id;
    });
    long long covered=left;
    int i=0;
    std::vector<int>chosen;
    while(covered<right){
        long long farthest=covered;
        int best=-1;
        while(i<n&&a[i].l<=covered){
            if(a[i].r>farthest){
                farthest=a[i].r;
                best=a[i].id;
            }
            ++i;
        }
        if(best==-1){
            std::cout<<"IMPOSSIBLE\n";
            return 0;
        }
        chosen.push_back(best);
        covered=farthest; // Every unused scanned interval ends no farther than this choice.
    }
    std::cout<<chosen.size()<<'\n';
    for(int j=0;j<(int)chosen.size();++j){
        std::cout<<chosen[j]<<(j+1==(int)chosen.size()?'\n':' ');
    }
    if(chosen.empty()){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log n) preprocessing sort and O(n) scan because each interval is consumed once. O(n) input/chosen-ID storage. No loop proportional to the numeric target length is used.

Example input and output

Read n L R (0≤n≤100000, −10^9≤L≤R≤10^9), then n intervals with −10^9≤left≤right≤10^9. Print minimum count and chosen IDs, or IMPOSSIBLE. Empty target needs zero choices.

Input

5 0 10
-1 3
0 5
3 7
5 10
7 12

Output

2
2 4

The first choice reaches 5 and the second reaches 10; no single interval covers the entire target.

Practical applications

Use for minimum equal-cost continuous coverage, sprinkler-like ranges and extending reachable frontiers. Activity selection chooses earliest finish to preserve free space; covering chooses farthest finish to maximize already-covered space. Their objectives reverse the appropriate criterion.

Check your understanding

Which interval should be selected at the current frontier?

Put it into practice

Create an impossible gap and a case with several eligible but contained intervals.