Union of Integer Sets
National Olympiad — Municipal round
Submission name: set.cpp
Problem summary
Each of N sets contains every integer from Ai through Bi. Express their union as the minimum number of integer intervals, listed in increasing order.
Input
N, then N pairs Ai Bi.
Output
Number M of resulting intervals, then their M endpoint pairs in increasing order of left endpoint.
Constraints
1≤N≤10000; 1≤Ai<Bi≤10^9.
Worked example
An independently prepared example for this explanation.
Input
3 2 4 5 7 10 11
Output
2 2 7 10 11
Solution analysis
- Sort intervals by their left endpoint.
- Merge an interval whenever its start is at most the current end plus one; integer adjacency leaves no missing integer.
- Otherwise finish the current interval and begin a new one.
Why it works
After sorting, every next interval either extends the current consecutive block or starts beyond a missing integer. In the latter case no later interval can fill the gap, so a separate block is necessary.
Complexity: O(N log N) time and O(N) space.
Watch out. Merge adjacent integer intervals as well as overlapping ones.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: After sorting, every next interval either extends the current consecutive block or starts
// beyond a missing integer. In the latter case no later interval can fill the gap, so a separate block
// is necessary.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<iterator>
using namespace std;
int main(){
int n;
cin>>n;
vector<pair<long long,long long>>a(n),b;
for(auto&[l,r]:a){
cin>>l>>r;
}
sort(a.begin(),a.end());
for(auto[l,r]:a){
if(b.empty()||l>b.back().second+1){
b.push_back({l,r});
}
else{
b.back().second=max(b.back().second,r);
}
}
cout<<b.size()<<'\n';
for(auto[l,r]:b){
cout<<l<<' '<<r<<'\n';
}
}