Most-Intersecting Segment
National Olympiad — Municipal round (2020 season)
Submission name: seg.cpp
Problem summary
Find the maximum number of other closed intervals intersected by any one input interval. Sharing an endpoint counts as intersection.
Input
n, then n left/right pairs.
Output
Largest intersection-neighbour count.
Constraints
1 ≤ n < 1000; 1 ≤ left < right < 10000; no identical intervals.
Worked example
Input and output for the worked example discussed below.
Input
5 1 4 3 6 2 5 1 2 6 7
Output
3
Solution analysis
- Closed intervals [a,b],[c,d] intersect exactly when max(a,c)≤min(b,d). This condition includes endpoint contact.
- Test every unordered pair once and increment both intervals’ counters when they meet. Take the maximum final counter.
- Sample interval [1,4] meets three others. Interval [3,6] also meets [6,7] at its endpoint. With a single interval the count is zero.
Why it works
Each intersecting pair contributes exactly one neighbour to both of its intervals.
Complexity: O(n²) time and O(n) space, with fewer than half a million pairs.
Watch out. Use ≤ rather than < and exclude self-intersection. The answer is not the total intersecting pair count.
Commented C++17 solution
An independently written complete program with standard headers.
// Each intersecting pair contributes exactly one neighbour to both of its intervals.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
int count;
cin>>count;
vector<pair<int,int>>intervals(count);
for(auto&interval:intervals){
cin>>interval.first>>interval.second;
}
vector<int>hits(count);
for(int first=0;first<count;first++){
for(int second=first+1;second<count;second++){
if(max(intervals[first].first,intervals[second].first)<=
min(intervals[first].second,intervals[second].second)){
hits[first]++;
hits[second]++;
}
}
}
cout<<*max_element(hits.begin(),hits.end())<<'\n';
}