Maximum Segment Coverage
National Olympiad — Municipal round
Submission name: cover.cpp
Problem summary
Given segments with integer endpoints, find the maximum number covering the interior of any unit interval (j,j+1), and the total length covered by exactly this maximum number.
Input
n, then n pairs xᵢ yᵢ with xᵢ<yᵢ.
Output
The maximum coverage on the first line and its total covered length on the second.
Constraints
0 < n < 50,000; 0 < xᵢ < yᵢ < 10,000,000.
Worked example
An independently prepared example for this explanation.
Input
3 1 5 3 7 4 6
Output
3 1
Solution analysis
- Create +1 at every left endpoint and −1 at every right endpoint.
- Sort and combine all events at each coordinate. The resulting count applies to the open interval until the next event.
- Reset the accumulated length upon a new maximum, and add interval lengths when the maximum is matched.
Why it works
Coverage changes only at endpoints and is constant between consecutive distinct endpoints. Summing those intervals with maximum coverage gives precisely the requested total, without counting zero-length endpoint intersections.
Watch out. Intervals that merely meet at an endpoint do not overlap over positive length.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Coverage changes only at endpoints and is constant between consecutive distinct endpoints.
// Summing those intervals with maximum coverage gives precisely the requested total, without counting
// zero-length endpoint intersections.
#include<iostream>
#include<map>
#include<iterator>
using namespace std;
int main(){
int n;
cin>>n;
map<int,int>ev;
while(n--){
int a,b;
cin>>a>>b;
ev[a]++;
ev[b]--;
}
int cover=0,best=0;
long long length=0;
for(auto it=ev.begin();it!=ev.end();it++){
cover+=it->second;
auto next=std::next(it);
if(next==ev.end()){
break;
}
long long len=next->first-it->first;
if(cover>best){
best=cover;
length=len;
}
else if(cover==best){
length+=len;
}
}
cout<<best<<'\n'<<length<<'\n';
}