Entero máximo ocurrido en n rangos | Conjunto-3

Dados N rangos de la forma L a R , la tarea es encontrar el entero máximo ocurrido en todos los rangos. Si existe más de uno de estos enteros, imprima el más pequeño.  

Ejemplos: 

Entrada: puntos[] = { {1, 6}, {2, 3}, {2, 5}, {3, 8} } 
Salida: 3 
Explicación: 
1 ocurre en 1 rango {1, 6} 
2 ocurre 3 en 3 rango {1, 6}, {2, 3}, {2, 5} 
3 ocurren 4 en 4 rango {1, 6}, {2, 3}, {2, 5}, {3, 8} 
4 ocurren 3 en 3 rango {1, 6}, {2, 5}, {3, 8} 
5 ocurren 3 en 3 rango {1, 6}, {2, 5}, {3, 8} 
6 ocurren 2 en 2 rango {1, 6}, {3, 8} 
7 ocurre 1 en 1 rango {3, 8} 
8 ocurre 1 en 1 rango {3, 8}
Por lo tanto, el entero más ocurrido es 3.

Entrada: puntos[] = { {1, 4}, {1, 9}, {1, 2}}; 
Salida: 1

Enfoque: Este es el enfoque improvisado de Máximo número entero ocurrido en n rangos . La idea principal es usar la compresión de coordenadas usando Hashing . Por lo tanto, no es necesario crear una array de frecuencias que exceda el límite de memoria para rangos grandes. A continuación se muestra el algoritmo paso a paso para resolver este problema: 

1. Inicialice los puntos de nombre de un mapa ordenado , para realizar un seguimiento de los puntos de inicio y fin de los rangos dados. 
2. Aumente el valor del punto[L] en 1 , para cada índice inicial del rango dado.
3. Disminuya el valor del punto [R+1] en 1, para cada índice final del rango dado.
4. Iterar el mapa en el orden creciente del valor de los puntos. Tenga en cuenta que la frecuencia[punto actual] = frecuencia[punto anterior] + puntos[punto actual] . Mantener el valor de la frecuencia del punto actual en una variable cur_freq .
5. El punto con el valor máximo de cur_freq será la respuesta.
6. Guarde el índice y devuélvalo.

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the most
// occurred element in given ranges
void maxOccurring(int range[][2], int n)
{
    // STL map for storing start
    // and end points
    map<int, int> points;
 
    for (int i = 0; i < n; i++) {
        int l = range[i][0];
        int r = range[i][1];
 
        // Increment at starting point
        points[l]++;
 
        // Decrement at ending point
        points[r + 1]--;
    }
 
    // Stores current frequency
    int cur_freq = 0;
 
    // Store element with maximum frequency
    int ans = 0;
 
    // Frequency of the current ans
    int freq_ans = 0;
 
    for (auto x : points) {
        // x.first denotes the current
        // point and x.second denotes
        // points[x.first]
        cur_freq += x.second;
 
        // If frequency of x.first is
        // greater that freq_ans
        if (cur_freq > freq_ans) {
            freq_ans = cur_freq;
            ans = x.first;
        }
    }
 
    // Print Answer
    cout << ans;
}
 
// Driver code
int main()
{
    int range[][2]
        = { { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 8 } };
    int n = sizeof(range) / sizeof(range[0]);
 
    // Function call
    maxOccurring(range, n);
 
    return 0;
}

// Java program of the above approach
import java.util.*;
 
class GFG{
 
// Function to print the most
// occurred element in given ranges
static void maxOccurring(int range[][], int n)
{
    // STL map for storing start
    // and end points
    HashMap<Integer,Integer> points = new HashMap<Integer,Integer>();
 
    for (int i = 0; i < n; i++) {
        int l = range[i][0];
        int r = range[i][1];
 
        // Increment at starting point
        if(points.containsKey(l)){
            points.put(l, points.get(l)+1);
        }
        else{
            points.put(l, 1);
 
        // Decrement at ending point
            if(points.containsKey(r + 1)){
                points.put(r + 1, points.get(r + 1)-1);
            }
    }
    }
    // Stores current frequency
    int cur_freq = 0;
 
    // Store element with maximum frequency
    int ans = 0;
 
    // Frequency of the current ans
    int freq_ans = 0;
 
    for (Map.Entry<Integer,Integer> entry :points.entrySet()) {
        // x.first denotes the current
        // point and x.second denotes
        // points[x.first]
        cur_freq += entry.getValue();
 
        // If frequency of x.first is
        // greater that freq_ans
        if (cur_freq > freq_ans) {
            freq_ans = cur_freq;
            ans = entry.getKey();
        }
    }
 
    // Print Answer
    System.out.print(ans);
}
 
// Driver code
public static void main(String[] args)
{
    int range[][]
        = { { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 8 } };
    int n = range.length;
 
    // Function call
    maxOccurring(range, n);
 
}
}
 
// This code is contributed by Princi Singh

# Python 3 program of the above approach
 
# Function to print the most
# occurred element in given ranges
def maxOccurring(range1, n):
   
    # STL map for storing start
    # and end points
    points = {}
 
    for i in range(n):
        l = range1[i][0]
        r = range1[i][1]
 
        # Increment at starting point
        if l in points:
            points[l] += 1
        else:
            points[l] = 1
 
        # Decrement at ending point
        if r+1 in points:
            points[r + 1] -= 1
        else:
            points[r+1] = 0
 
    # Stores current frequency
    cur_freq = 0
 
    # Store element with maximum frequency
    ans = 0
 
    # Frequency of the current ans
    freq_ans = 0
 
    for key,value in points.items():
        # x.first denotes the current
        # point and x.second denotes
        # points[x.first]
        cur_freq += value
 
        # If frequency of x.first is
        # greater that freq_ans
        if (cur_freq > freq_ans):
            freq_ans = cur_freq
            ans = key
 
    # Print Answer
    print(ans)
 
# Driver code
if __name__ == '__main__':
    range1 = [[1, 6],[2, 3],[2, 5],[3, 8]]
    n = len(range1)
 
    # Function call
    maxOccurring(range1, n)
     
    # This code is contributed by ipg2016107.

// C# program of the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to print the most
// occurred element in given ranges
static void maxOccurring(int [,]range, int n)
{
    // STL map for storing start
    // and end points
    Dictionary<int, int> points = new Dictionary<int,int>();
 
    for (int i = 0; i < n; i++) {
        int l = range[i,0];
        int r = range[i,1];
 
        // Increment at starting point
      if(points.ContainsKey(l))
        points[l]++;
       
      else
        points.Add(l,1);
 
        // Decrement at ending point
        if(points.ContainsKey(r+1))
          points[r + 1]--;
        else
          points.Add(r+1,0);
    }
 
    // Stores current frequency
    int cur_freq = 0;
 
    // Store element with maximum frequency
    int ans = 0;
 
    // Frequency of the current ans
    int freq_ans = 0;
 
    foreach(KeyValuePair<int,int> entry in points) {
        // x.first denotes the current
        // point and x.second denotes
        // points[x.first]
        cur_freq += entry.Value;
 
        // If frequency of x.first is
        // greater that freq_ans
        if (cur_freq > freq_ans) {
            freq_ans = cur_freq;
            ans = entry.Key;
        }
    }
 
    // Print Answer
    Console.Write(ans);
}
 
// Driver code
public static void Main()
{
    int [,]range = {{1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 8 } };
    int n = 4;
 
    // Function call
    maxOccurring(range, n);
}
}
 
// This code is contributed by ipg2016107.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to print the most
        // occurred element in given ranges
        function maxOccurring(range, n)
        {
         
            // STL map for storing start
            // and end points
            let points = new Map();
 
            for (let i = 0; i < n; i++) {
                let l = range[i][0];
                let r = range[i][1];
 
                // Increment at starting point
                if (points.has(l))
                    points.set(points.get(l), points.get(l) + 1);
                else
                    points.set(l, 1);
 
                // Decrement at ending point
                if (points.has(r + 1)) {
                    points.set(points.get(r + 1), points.get(r + 1) - 1);
                }
 
            }
 
            // Stores current frequency
            let cur_freq = 0;
 
            // Store element with maximum frequency
            let ans = 0;
 
            // Frequency of the current ans
            let freq_ans = 0;
 
            for (let [key, value] of points)
            {
             
                // x.first denotes the current
                // point and x.second denotes
                // points[x.first]
                cur_freq = cur_freq + value;
 
                // If frequency of x.first is
                // greater that freq_ans
                if (cur_freq > freq_ans) {
                    freq_ans = cur_freq;
                    ans = key;
                }
            }
 
            // Print Answer
            document.write(ans);
        }
 
        // Driver code
        let range
            = [[1, 6], [2, 3], [2, 5], [3, 8]];
        let n = range.length;
 
        // Function call
        maxOccurring(range, n);
 
// This code is contributed by Potta Lokesh
    </script>

3

Complejidad de tiempo: O(n Logn)
Complejidad de espacio: O(n)