Número máximo de intervalos superpuestos

Dados diferentes intervalos, la tarea es imprimir el número máximo de superposición entre estos intervalos en cualquier momento.

Ejemplos: 

Entrada: v = {{1, 2}, {2, 4}, {3, 6}} 
Salida: 2 
La superposición máxima es 2 (entre (1 2) y (2 4) o entre (2 4) y ( 3 6)) 
 

Entrada: v = {{1, 8}, {2, 5}, {5, 6}, {3, 7}} 
Salida: 4 
La superposición máxima es 4 (entre (1, 8), (2, 5) , (5, 6) y (3, 7))
 

Acercarse: 

• La idea es almacenar coordenadas en un nuevo vector de par mapeado con caracteres ‘x’ e ‘y’, para identificar coordenadas.
• Ordenar el vector.
• Atraviese el vector, si se encuentra una coordenada x, significa que se agrega un nuevo rango, así que actualice el conteo y si se encuentra la coordenada y, significa que se resta un rango.
• Actualice el valor de conteo para cada nueva coordenada y tome el máximo.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program that print maximum
// number of overlap
// among given ranges
#include <bits/stdc++.h>
using namespace std;
 
// Function that print maximum
// overlap among ranges
void overlap(vector<pair<int, int> > v)
{
    // variable to store the maximum
    // count
    int ans = 0;
    int count = 0;
    vector<pair<int, char> > data;
 
    // storing the x and y
    // coordinates in data vector
    for (int i = 0; i < v.size(); i++) {
 
        // pushing the x coordinate
        data.push_back({ v[i].first, 'x' });
 
        // pushing the y coordinate
        data.push_back({ v[i].second, 'y' });
    }
 
    // sorting of ranges
    sort(data.begin(), data.end());
 
    // Traverse the data vector to
    // count number of overlaps
    for (int i = 0; i < data.size(); i++) {
 
        // if x occur it means a new range
        // is added so we increase count
        if (data[i].second == 'x')
            count++;
 
        // if y occur it means a range
        // is ended so we decrease count
        if (data[i].second == 'y')
            count--;
 
        // updating the value of ans
        // after every traversal
        ans = max(ans, count);
    }
 
    // printing the maximum value
    cout << ans << endl;
}
 
// Driver code
int main()
{
    vector<pair<int, int> > v
        = { { 1, 2 }, { 2, 4 }, { 3, 6 } };
    overlap(v);
    return 0;
}

// Java program that print maximum
// number of overlap among given ranges
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
     
static class pair
{
    int first;
    char second;
     
    pair(int first, char second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function that print maximum
// overlap among ranges
static void overlap(int[][] v)
{
     
    // Variable to store the maximum
    // count
    int ans = 0;
    int count = 0;
    ArrayList<pair> data = new ArrayList<>();
     
    // Storing the x and y
    // coordinates in data vector
    for(int i = 0; i < v.length; i++)
    {
         
        // Pushing the x coordinate
        data.add(new pair(v[i][0], 'x'));
   
        // pushing the y coordinate
        data.add(new pair(v[i][1], 'y'));
    }
     
    // Sorting of ranges
    Collections.sort(data, (a, b) -> a.first - b.first);
   
    // Traverse the data vector to
    // count number of overlaps
    for(int i = 0; i < data.size(); i++)
    {
         
        // If x occur it means a new range
        // is added so we increase count
        if (data.get(i).second == 'x')
            count++;
   
        // If y occur it means a range
        // is ended so we decrease count
        if (data.get(i).second == 'y')
            count--;
   
        // Updating the value of ans
        // after every traversal
        ans = Math.max(ans, count);
    }
   
    // Printing the maximum value
    System.out.println(ans);
}
 
// Driver code
public static void main(String[] args)
{
    int[][] v = { { 1, 2 },
                  { 2, 4 },
                  { 3, 6 } };
    overlap(v);
}
}
 
// This code is contributed by offbeat

# Python3 program that print maximum
# number of overlap
# among given ranges
 
# Function that print maximum
# overlap among ranges
def overlap(v):
 
    # variable to store the maximum
    # count
    ans = 0
    count = 0
    data = []
 
    # storing the x and y
    # coordinates in data vector
    for i in range(len(v)):
 
        # pushing the x coordinate
        data.append([v[i][0], 'x'])
 
        # pushing the y coordinate
        data.append([v[i][1], 'y'])
 
    # sorting of ranges
    data = sorted(data)
 
    # Traverse the data vector to
    # count number of overlaps
    for i in range(len(data)):
 
        # if x occur it means a new range
        # is added so we increase count
        if (data[i][1] == 'x'):
            count += 1
 
        # if y occur it means a range
        # is ended so we decrease count
        if (data[i][1] == 'y'):
            count -= 1
 
        # updating the value of ans
        # after every traversal
        ans = max(ans, count)
 
    # printing the maximum value
    print(ans)
 
# Driver code
v = [ [ 1, 2 ], [ 2, 4 ], [ 3, 6 ] ]
overlap(v)
 
# This code is contributed by mohit kumar 29

<script>
 
// Javascript program that print maximum
// number of overlap among given ranges
 
// Function that print maximum
// overlap among ranges
function overlap(v)
{
     
    // Variable to store the maximum
    // count
    var ans = 0;
    var count = 0;
    var data = [];
 
    // Storing the x and y
    // coordinates in data vector
    for(var i = 0; i < v.length; i++)
    {
         
        // Pushing the x coordinate
        data.push([v[i][0], 'x']);
 
        // Pushing the y coordinate
        data.push([v[i][1], 'y']);
    }
 
    // Sorting of ranges
    data.sort();
 
    // Traverse the data vector to
    // count number of overlaps
    for(var i = 0; i < data.length; i++)
    {
         
        // If x occur it means a new range
        // is added so we increase count
        if (data[i][1] == 'x')
            count++;
 
        // If y occur it means a range
        // is ended so we decrease count
        if (data[i][1] == 'y')
            count--;
 
        // Updating the value of ans
        // after every traversal
        ans = Math.max(ans, count);
    }
 
    // Printing the maximum value
    document.write(ans + "<br>");
}
 
// Driver code
var v = [ [ 1, 2 ], [ 2, 4 ], [ 3, 6 ] ];
overlap(v);
 
// This code is contributed by rutvik_56
 
</script>

2