Find number of common segments and its common point

Given an array A[ ] of N segments find any point common to maximum number of segments and also find the number of segments which it is common to. The segments are in the form [L, R].

Examples:

Input: 
N = 3, A[ ] = {{2, 4}, {-1, 3}, {-5, 1}}
Output: 
Point 0 is common to 2 segments( This is not the only answer )
Explanation: 
Point -5, -4, -3, -2 and 4 are common to 1 segment,
Point -1, 0, 1, 2 and 3 are common to 2 segments, hence maximum is 2.

Input: 
N = 4, A[ ] = {{4, 6}, {5, 7}, {8, 10}, {1, 5}, {3, 9}}
Output: 
Point 5 is common to 4 segments
Explanation:  
Point 1, 2 and 10 are common to 1 segment,
Point 3, 7, 8 and 9 are common to 2 segments,
Point 4 and 6 are common to 3 segments,
Point 5 is common to 4 segments, hence maximum is 4.

Approach:
It can be proved that one of the starting points will always be common to maximum number of segments.
To find the point common to maximum number of segments, first we need to count the change in number of segments for every point that is either a starting point or an ending point of a segment.

We can do this by iterating through the starting and ending points and increase the counter for that point for every starting point and decrease the counter for every ending point (Since the segments are in the form [L, R], i.e. L and R inclusive, we need to decrease the counter at R + 1).

We can use std::map to do this. Now we can simply iterate (points are already sorted in ascending order due to use of map) through the map and for each point add the counter for that point to an answer variable and update the final answer variable and point using the answer variable if necessary.

Implementation in C++:

// C++ program to find point common to maximum number of
// segments and number of segments it is common to
#include <bits/stdc++.h>
using namespace std;

// Function to find point common to maximum number of
// segments and number of segments it is common to
void findPoint(int N, pair<int, int> A[])
{
    // Initializing maximum count of segments
    int finalCount = 0;

    // Variable to store the point common to maximum
    // segments and variable to keep count of segments
    int point, count = 0;

    // Map to store change in number of segments for
    // every point that is either starting or ending
    // point of a segment
    map<int, int> counter;

    // Iterating through the segments and calculating
    // change in number of segments for starting and
    // ending point
    for (int i = 0; i < N; i++) {
        // Increasing the counter for starting point
        counter[A[i].first]++;

        // Decreasing the counter for ending point
        counter[A[i].second + 1]--;
    }

    // Iterating through all starting and ending points
    // and keeping count of segments
    for (auto i : counter) {
        count += i.second;

        // Updating the answer if necessary
        if (count > finalCount) {
            finalCount = count;
            point = i.first;
        }
    }
    // Print the point common to maximum number of
    // segments and the number of segments it is
    // common to
    cout << "Point " << point << " is common to "
         << finalCount << " segments" << endl;
}

// Driver Code
int main()
{
    int N = 3;
    pair<int, int> A[] = { { 2, 4 }, { -1, 3 }, { -5, 1 } };
    findPoint(N, A);

    N = 5;
    pair<int, int> B[] = {
        { 4, 6 }, { 5, 7 }, { 8, 10 }, { 1, 5 }, { 3, 9 } };
    findPoint(N, B);

    return 0;
}

Output:

Point -1 is common to 2 segments
Point 5 is common to 4 segments

Time Complexity: O(N*logN), due to use of std::map.