Interval Scheduling and Interval Merging

Interval problems can look similar while asking for different objects. Merging returns the union covered by all intervals; scheduling selects a largest compatible subset of original intervals. Merging does not choose activities and can create an interval that was never an input. The primary program computes union components and length; a separate runnable example reuses earliest-finish scheduling so students can compare the two outputs directly.

Prerequisites: Activity Selection; sorting and loop invariants.

Build the idea

1. State the union contract

   Normalize endpoint order, treat intervals as half-open [l,r), and discard empty intervals l=r. Sort by start, then end. A merged component records a connected piece of the covered union; touching intervals can join because [a,b)∪[b,c)=[a,c). This is compatible with scheduling’s decision that two touching activities may both be selected.

2. Extend the current component

   Process intervals in start order. If the next start exceeds the current component’s end, finalize that component and begin another. Otherwise extend the end to max(currentEnd,nextEnd). A contained interval changes nothing. result.back() is sufficient because all earlier components end before the current one and can never be reached by a future interval starting still farther right.

   $$\mathrm{unionLength}=\Sigma (\mathrm{component}.\mathrm{end}-\mathrm{component}.\mathrm{start})$$

3. Correctness proof: maintain the processed union

   After each step, result is a sorted disjoint-component representation of exactly the processed input union. A new interval either joins the final component or starts beyond it; start order prevents any third possibility involving an earlier component. Updating the maximum end preserves all covered points and introduces no gap coverage. Induction proves the final union. This is an invariant-based correctness proof, not the activity-selection exchange.

4. Trace and compare

   For [1,3),[2,5),[5,7),[9,10), the first three merge to [1,7); the last remains separate. Union length is 6+1=7. A compatible scheduling solution might instead choose [1,3),[5,7),[9,10), keeping original activities. The merged [1,7) is not a valid substitute when the problem asks which original activities to attend.

5. Use the right sorted order

   Start order is natural for union components; finish order exposes the safe first activity for maximum count. The supplementary program includes its own headers and main and expects positive-duration activity intervals. It is not a fragment dependent on the merging implementation. Both algorithms are O(n log n), but sharing a complexity does not make their goals or proofs interchangeable.

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
int main(){
    int n;
    std::cin>>n;
    std::vector<std::pair<long long,long long>>intervals;
    for(int i=0;i<n;++i){
        long long l,r;
        std::cin>>l>>r;
        if(l>r){
            std::swap(l,r);
        }
        if(l<r){
            intervals.push_back({l,r});
        }
    }
    std::sort(intervals.begin(),intervals.end());
    std::vector<std::pair<long long,long long>>result;
    for(auto[l,r]:intervals){
        if(result.empty()||l>result.back().second){
            result.push_back({l,r});
        }
        else{
            result.back().second=std::max(result.back().second,r);
        }
    }
    long long length=0;
    for(auto[l,r]:result){
        length+=r-l; // Connected/touching components of the half-open union.
    }
    std::cout<<result.size()<<' '<<length<<'\n';
    for(auto[l,r]:result){
        std::cout<<l<<' '<<r<<'\n';
    }
}

Complexity analysis

O(n log n) sorting and O(n) merging, O(n) input/result space. The total union length is at most 2·10^9 under the coordinate contract, and long long also supports endpoint subtraction safely. The supplementary scheduling program has the same asymptotic costs.

Example input and output

Read n (0..100000), then endpoint pairs within ±10^9. Normalize reversed endpoints and ignore empty half-open intervals. Print component count and union length, followed by merged components.

Input

4
1 3
2 5
5 7
9 10

Output

2 7
1 7
9 10

The first three intervals form one covered component, including the touch at 5; the remaining component has length 1.

Read n (0..100000), then n start finish pairs with −10^9≤start<finish≤10^9. Print maximum count and original IDs in execution order. Touching endpoints are compatible.

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
struct Activity{
    long long start,finish;
    int id;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Activity>a(n);
    for(int i=0;i<n;++i){
        std::cin>>a[i].start>>a[i].finish;
        a[i].id=i+1;
    }
    std::sort(a.begin(),a.end(),[](Activity a,Activity b){
        return a.finish!=b.finish?a.finish<b.finish:a.id<b.id;
    });
    long long end=std::numeric_limits<long long>::lowest();
    std::vector<int>selected;
    for(Activity x:a){
        if(x.start>=end){
            selected.push_back(x.id);
            end=x.finish;
        } // Half-open activities may touch.
    }
    std::cout<<selected.size()<<'\n';
    for(int i=0;i<(int)selected.size();++i){
        std::cout<<selected[i]<<(i+1==(int)selected.size()?'\n':' ');
    }
    if(selected.empty()){
        std::cout<<'\n';
    }
}

Input

5
1 4
3 5
0 6
5 7
7 9

Output

3
1 4 5

Earliest finish chooses (1,4), then (5,7), then (7,9). The last pair touch but do not overlap.

Complexity: O(n log n) for sorting and O(n) for the acceptance scan. O(n) input/output storage and O(1) extra decision state. If already finish-sorted, the scan alone is linear.

Practical applications

Use merging for coverage, blocked-time compression and union-length queries. Use activity selection for maximum compatible count, meeting rooms to retain all meetings, and weighted DP when intervals have profits. First identify which result the problem actually wants.

Check your understanding

Can a merged component always be chosen as one original activity?

Put it into practice

Run merging and scheduling on the same four intervals and explain their different outputs.