Dada una array de intervalos arr[] de tamaño N , la tarea es encontrar el K -ésimo elemento más pequeño entre todos los elementos dentro de los intervalos de la array dada.
Ejemplos:
Entrada: arr[] = {{5, 11}, {10, 15}, {12, 20}}, K =12
Salida: 13
Explicación: Los elementos en la array dada de intervalos son: {5, 6, 7, 8, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 17, 18, 19, 20}.
Por lo tanto, el K th (=12 th ) elemento más pequeño es 13.Entrada: arr[] = {{5, 11}, {10, 15}, {12, 20}}, K = 7
Salida: 10
Enfoque ingenuo: el enfoque más simple es generar una nueva array que consta de todos los elementos de la array de intervalos. Ordenar la nueva array . Finalmente, devuelva el K -ésimo elemento más pequeño de la array .
Complejidad temporal: O(X*Log(X)), donde X es el número total de elementos en los intervalos.
Espacio auxiliar: O(X*log(X))
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar MinHeap . Siga los pasos a continuación para resolver el problema.
- Cree un MinHeap , digamos pq para almacenar todos los intervalos de la array dada para que devuelva el elemento mínimo entre todos los elementos de los intervalos restantes en O(1).
- Extraiga el intervalo mínimo del MinHeap y verifique si el elemento mínimo del intervalo emergente es menor que el elemento máximo del intervalo emergente. Si se determina que es cierto, inserte un nuevo intervalo {elemento mínimo del intervalo emergente + 1, elemento máximo del intervalo emergente} .
- Repita el paso anterior K – 1 veces.
- Finalmente, devuelva el elemento mínimo del intervalo emergente.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the Kth smallest
// element from an array of intervals
int KthSmallestNum(pair<int, int> arr[],
int n, int k)
{
// Store all the intervals so that it
// returns the minimum element in O(1)
priority_queue<pair<int, int>,
vector<pair<int, int> >,
greater<pair<int, int> > >
pq;
// Insert all Intervals into the MinHeap
for (int i = 0; i < n; i++) {
pq.push({ arr[i].first,
arr[i].second });
}
// Stores the count of
// popped elements
int cnt = 1;
// Iterate over MinHeap
while (cnt < k) {
// Stores minimum element
// from all remaining intervals
pair<int, int> interval
= pq.top();
// Remove minimum element
pq.pop();
// Check if the minimum of the current
// interval is less than the maximum
// of the current interval
if (interval.first < interval.second) {
// Insert new interval
pq.push(
{ interval.first + 1,
interval.second });
}
cnt++;
}
return pq.top().first;
}
// Driver Code
int main()
{
// Intervals given
pair<int, int> arr[]
= { { 5, 11 },
{ 10, 15 },
{ 12, 20 } };
// Size of the arr
int n = sizeof(arr) / sizeof(arr[0]);
int k = 12;
cout << KthSmallestNum(arr, n, k);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.io.*;
class GFG{
// Function to get the Kth smallest
// element from an array of intervals
public static int KthSmallestNum(int arr[][], int n,
int k)
{
// Store all the intervals so that it
// returns the minimum element in O(1)
PriorityQueue<int[]> pq = new PriorityQueue<>(
(a, b) -> a[0] - b[0]);
// Insert all Intervals into the MinHeap
for(int i = 0; i < n; i++)
{
pq.add(new int[]{arr[i][0],
arr[i][1]});
}
// Stores the count of
// popped elements
int cnt = 1;
// Iterate over MinHeap
while (cnt < k)
{
// Stores minimum element
// from all remaining intervals
int[] interval = pq.poll();
// Check if the minimum of the current
// interval is less than the maximum
// of the current interval
if (interval[0] < interval[1])
{
// Insert new interval
pq.add(new int[]{interval[0] + 1,
interval[1]});
}
cnt++;
}
return pq.peek()[0];
}
// Driver Code
public static void main(String args[])
{
// Intervals given
int arr[][] = { { 5, 11 },
{ 10, 15 },
{ 12, 20 } };
// Size of the arr
int n = arr.length;
int k = 12;
System.out.println(KthSmallestNum(arr, n, k));
}
}
// This code is contributed by hemanth gadarla
Python3
# Python3 program to implement # the above approach # Function to get the Kth smallest # element from an array of intervals def KthSmallestNum(arr, n, k): # Store all the intervals so that it # returns the minimum element in O(1) pq = [] # Insert all Intervals into the MinHeap for i in range(n): pq.append([arr[i][0], arr[i][1]]) # Stores the count of # popped elements cnt = 1 # Iterate over MinHeap while (cnt < k): # Stores minimum element # from all remaining intervals pq.sort(reverse = True) interval = pq[0] # Remove minimum element pq.remove(pq[0]) # Check if the minimum of the current # interval is less than the maximum # of the current interval if (interval[0] < interval[1]): # Insert new interval pq.append([interval[0] + 1, interval[1]]) cnt += 1 pq.sort(reverse = True) return pq[0][0] + 1 # Driver Code if __name__ == '__main__': # Intervals given arr = [ [ 5, 11 ], [ 10, 15 ], [ 12, 20 ] ] # Size of the arr n = len(arr) k = 12 print(KthSmallestNum(arr, n, k)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# Program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
// Function to get the Kth smallest
// element from an array of intervals
static int KthSmallestNum(int[,] arr, int n, int k)
{
// Store all the intervals so that it
// returns the minimum element in O(1)
ArrayList pq = new ArrayList();
// Insert all Intervals into the MinHeap
for(int i = 0; i < n; i++)
{
pq.Add(new Tuple<int,int>(arr[i,0], arr[i,1]));
}
// Stores the count of
// popped elements
int cnt = 1;
// Iterate over MinHeap
while (cnt < k)
{
// Stores minimum element
// from all remaining intervals
pq.Sort();
pq.Reverse();
Tuple<int,int> interval = (Tuple<int,int>)pq[0];
// Remove minimum element
pq.RemoveAt(0);
// Check if the minimum of the current
// interval is less than the maximum
// of the current interval
if (interval.Item1 < interval.Item2)
{
// Insert new interval
pq.Add(new Tuple<int,int>(interval.Item1 + 1, interval.Item2));
}
cnt += 1;
}
pq.Sort();
pq.Reverse();
return ((Tuple<int,int>)pq[0]).Item1 + 1;
}
// Driver code
static void Main()
{
// Intervals given
int[,] arr = { { 5, 11 },
{ 10, 15 },
{ 12, 20 } };
// Size of the arr
int n = arr.GetLength(0);
int k = 12;
Console.WriteLine(KthSmallestNum(arr, n, k));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to get the Kth smallest
// element from an array of intervals
function KthSmallestNum(arr, n, k)
{
// Store all the intervals so that it
// returns the minimum element in O(1)
var pq = [];
// Insert all Intervals into the MinHeap
for(var i = 0; i < n; i++)
{
pq.push([arr[i][0], arr[i][1]]);
}
// Stores the count of
// popped elements
var cnt = 1;
// Iterate over MinHeap
while (cnt < k)
{
// Stores minimum element
// from all remaining intervals
pq.sort((a,b)=>{
if(a[0]==b[0])
return a[1]-b[1]
return a[0]-b[0]
});
var interval = pq[0];
// Remove minimum element
pq.shift();
// Check if the minimum of the current
// interval is less than the maximum
// of the current interval
if (interval[0] < interval[1])
{
// Insert new interval
pq.push([interval[0] + 1, interval[1]]);
}
cnt += 1;
}
pq.sort((a,b) =>
{
if(a[0]==b[0])
return a[1]-b[1]
return a[0]-b[0]
});
return (pq[0])[0];
}
// Driver code
// Intervals given
var arr = [ [ 5, 11 ],
[ 10, 15 ],
[ 12, 20 ] ];
// Size of the arr
var n = arr.length;
var k = 12;
document.write(KthSmallestNum(arr, n, k));
</script>
Producción:
13
Complejidad de tiempo: O(K*logK)
Espacio auxiliar: O(N)