Proficient.
Put your skills to the test.

Problem summary

Find the number of connected components of the union of closed intervals, and the length of its longest component.

Constraints

0 < n < 1000; 0 < a < b < 10000.

Worked example

An independently prepared example for this explanation.

6
11 12
1 3
6 7
2 6
12 13
11 12

2 6

Solution analysis

1. Sort the intervals by left endpoint. Keep the endpoints of the current union component.
2. An interval whose left endpoint is at most the current right endpoint belongs to the same component, including when it only touches an endpoint. Otherwise finish the component and begin another.
3. In the example, [1,3], [2,6] and [6,7] merge into [1,7], of length 6. The remaining intervals merge into [11,13], giving two components.

Why it works

In sorted order, no future interval can bridge a gap that starts before its own left endpoint. Thus each strict gap finalizes one component. Overlapping or touching intervals extend precisely the current component. Recording each finalized length gives the maximum.

Watch out. Touching closed intervals merge. The geometric length is right−left, without adding one.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Sort the intervals by left endpoint.
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<pair<int,int>>intervals(n);
    for(auto&interval:intervals){
        cin>>interval.first>>interval.second;
    }
    sort(intervals.begin(),intervals.end());
    int left=intervals[0].first;
    int right=intervals[0].second;
    int count=1;
    int longest=0;
    for(int i=1;i<n;++i){
        if(intervals[i].first<=right){
            right=max(right,intervals[i].second);
        }
        else{
            longest=max(longest,right-left);
            ++count;
            left=intervals[i].first;
            right=intervals[i].second;
        }
    }
    longest=max(longest,right-left);
    cout<<count<<' '<<longest<<'\n';
}