Dada una array 2D arr[][] de la forma {inicio, fin} que representa la hora de inicio y finalización de N reuniones, también dadas dos arrays entrada[] y existe[] que representan las horas de apertura y cierre de la sala de reuniones respectivamente, la tarea es encontrar el tiempo mínimo durante el cual se puede asistir a una reunión. Si no es posible asistir a ninguna reunión, imprima -1 .
Ejemplos:
Entrada: arr[][] = {{15, 19}, {5, 10}, {7, 25}}, entrada[] = {4, 13, 25, 2}, exist[] = {10, 21 }
Salida: 6
Explicación:
Reunión 1: Ingrese a la hora 13, asista a la reunión en el intervalo (15, 19) y salga a la hora 21. Por lo tanto, tiempo total dedicado a la reunión = 21 – 13 = 8.
Reunión 2 : Ingrese a la hora 4, asista a la reunión en (5, 10) y salga a la hora 10. Por lo tanto, tiempo total dedicado a la reunión = 10 – 4 = 6.
Reunión 3: Ingrese a la hora 4, asista a la reunión en el intervalo (7, 25). Pero después de la hora 25 no hay hora de cierre. Por lo tanto, el tiempo total empleado es infinito.
Por lo tanto, las unidades mínimas de tiempo que se pueden emplear para asistir a una reunión son 6.Entrada: arr[][] = {{1, 2}}, entrada[] = {1, 2}, exist[] = {3, 4}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar arr[][] y para cada intervalo {start i , end i } , encuentre el valor que sea menor o igual que arr[i][0] en la array entrada[] . Además, encuentre el valor que es mayor o igual que arr[i][1] en la array exist[] . Finalmente, imprima el tiempo mínimo para asistir exactamente a una reunión.
Complejidad de tiempo: O(N*max(P, M)), donde M y P son el tamaño de las arrays de entrada[] y existencia[].
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el algoritmo de clasificación y la técnica de búsqueda binaria .
Siga los pasos a continuación para resolver el problema:
- Ordene las arrays entry[] y exist[] en orden creciente.
- Inicialice una variable y almacene el tiempo mínimo para asistir exactamente a una reunión.
- Recorra la array y, para cada intervalo de las reuniones, encuentre el valor que es menor o igual que el inicio de i en la array de entrada[] usando el límite superior y encuentre el valor que es mayor o igual que el final de i en la existencia[ ] array usando lower_bound .
- Finalmente, imprima el tiempo mínimo para asistir exactamente a una reunión.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum time to
// attend exactly one meeting
int minTime(int meeting[][2], int n,
vector<int> entrance, int m,
vector<int> &exit, int p)
{
// Stores minimum time to attend
// exactly one meeting
int ans = INT_MAX;
// Sort entrance[] array
sort(entrance.begin(), entrance.end());
// Sort exit[] time
sort(exit.begin(), exit.end());
// Traverse meeting[][]
for (int i = 0; i < n; i++) {
// Stores start time of
// current meeting
int u = meeting[i][0];
// Stores end time of
// current meeting
int v = meeting[i][1];
// Find just greater value of
// u in entrance[]
auto it1
= upper_bound(entrance.begin(),
entrance.end(), u);
// Find just greater or equal value
// of u in entrance[]
auto it2
= lower_bound(exit.begin(),
exit.end(), v);
// Stores enter time to attend
// the current meeting
int start = it1
- entrance.begin() - 1;
// Stores exist time after
// attending the meeting
int end = it2 - exit.begin();
// Update start lies in range [0, m -1]
// and end lies in the range [0, p - 1]
if (start >= 0 && start < m &&
end >= 0 && end < p)
// Update ans
ans = min(ans,
exit[end] - entrance[start]);
}
// Return answer
return ans >= INT_MAX ? -1 : ans;
}
// Driver Code
int main()
{
// Stores interval of meeting
int meeting[][2]
= { { 15, 19 }, { 5, 10 }, { 7, 25 } };
// Stores entrance timings
vector<int> entrance = { 4, 13, 25, 2 };
// Stores exit timings
vector<int> exit = { 10, 25 };
// Stores total count of meetings
int n = (sizeof(meeting))
/ sizeof(meeting[0]);
// Stores total entrance timings
int m = entrance.size();
// Stores total exit timings
int p = exit.size();
// Minimum time
cout << minTime(meeting, n, entrance,
m, exit, p)
<< endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static Vector<Integer> exit =
new Vector<>();
// Function to find the
// minimum time to attend
// exactly one meeting
static int minTime(int meeting[][], int n,
int[] entrance, int m,
int p)
{
// Stores minimum time to attend
// exactly one meeting
int ans = Integer.MAX_VALUE;
// Sort entrance[] array
Arrays.sort(entrance);
// Sort exit[] time
Collections.sort(exit);
// Traverse meeting[][]
for (int i = 0; i < n; i++)
{
// Stores start time of
// current meeting
int u = meeting[i][0];
// Stores end time of
// current meeting
int v = meeting[i][1];
// Find just greater value of
// u in entrance[]
int it1 = upper_bound(entrance, 0,
entrance.length, u);
// Find just greater or equal
// value of u in entrance[]
int it2 = lowerBound(exit, 0,
exit.size(), v);
// System.out.println(exit.size());
// Stores enter time to attend
// the current meeting
int start = it1 - 1 ;
// Stores exist time after
// attending the meeting
int end = it2 ;
// Update start lies in range [0, m -1]
// and end lies in the range [0, p - 1]
if (start >= 0 && start < m &&
end >= 0 && end < p)
// Update ans
ans = Math.min(ans,
exit.get(end) -
entrance[start]);
}
// Return answer
return ans >= Integer.MAX_VALUE ?
-1 : ans;
}
static int upper_bound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low +
(high - low) / 2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
static int lowerBound(Vector<Integer> vec,
int low, int high,
int element)
{
int [] array =
new int[vec.size()];
int k = 0;
for(Integer val : vec)
{
array[k] = val;
k++;
}
// vec.clear();
while (low < high)
{
int middle = low +
(high - low) / 2;
if (element > array[middle])
{
low = middle + 1;
} else
{
high = middle;
}
}
return low;
}
// Driver Code
public static void main(String[] args)
{
// Stores interval of meeting
int meeting[][] = {{15, 19},
{5, 10},
{7, 25}};
// Stores entrance timings
int []entrance = {4, 13, 25, 2};
// Stores exit timings
exit.add(10);
exit.add(25);
// Stores total count of
// meetings
int n = meeting.length;
// Stores total entrance
// timings
int m = entrance.length;
// Stores total exit
// timings
int p = exit.size();
// Minimum time
System.out.print(minTime(meeting, n,
entrance, m,
p) + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach from bisect import bisect_left, bisect_right import sys # Function to find the minimum time to # attend exactly one meeting def minTime(meeting, n, entrance, m, exit, p): # Stores minimum time to attend # exactly one meeting ans = sys.maxsize # Sort entrance[] array entrance = sorted(entrance) # Sort exit[] time exit = sorted(exit) # Traverse meeting[][] for i in range(n): # Stores start time of # current meeting u = meeting[i][0] # Stores end time of # current meeting v = meeting[i][1] # Find just greater value of # u in entrance[] it1 = bisect_right(entrance, u) # Find just greater or equal value # of u in entrance[] it2 = bisect_left(exit, v) # Stores enter time to attend # the current meeting start = it1 - 1 # Stores exist time after # attending the meeting end = it2 # Update start lies in range [0, m -1] # and end lies in the range [0, p - 1] if (start >= 0 and start < m and end >= 0 and end < p): # Update ans ans = min(ans, exit[end] - entrance[start]) if ans >= sys.maxsize: ans = -1 # Return answer return ans # Driver Code if __name__ == '__main__': # Stores interval of meeting meeting = [ [ 15, 19 ], [ 5, 10 ], [ 7, 25 ] ] # Stores entrance timings entrance = [ 4, 13, 25, 2 ] # Stores exit timings exit = [ 10, 25 ] # Stores total count of meetings n = len(meeting) # Stores total entrance timings m = len(entrance) # Stores total exit timings p = len(exit) # Minimum time print(minTime(meeting, n, entrance, m, exit, p)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
static List<int> exit = new List<int>();
// Function to find the
// minimum time to attend
// exactly one meeting
static int minTime(int [,]meeting, int n,
int[] entrance, int m,
int p)
{
// Stores minimum time to attend
// exactly one meeting
int ans = int.MaxValue;
// Sort entrance[] array
Array.Sort(entrance);
// Sort exit[] time
exit.Sort();
// Traverse meeting[,]
for(int i = 0; i < n; i++)
{
// Stores start time of
// current meeting
int u = meeting[i, 0];
// Stores end time of
// current meeting
int v = meeting[i, 1];
// Find just greater value of
// u in entrance[]
int it1 = upper_bound(entrance, 0,
entrance.Length, u);
// Find just greater or equal
// value of u in entrance[]
int it2 = lowerBound(exit, 0,
exit.Count, v);
// Console.WriteLine(exit.Count);
// Stores enter time to attend
// the current meeting
int start = it1 - 1;
// Stores exist time after
// attending the meeting
int end = it2;
// Update start lies in range [0, m -1]
// and end lies in the range [0, p - 1]
if (start >= 0 && start < m &&
end >= 0 && end < p)
// Update ans
ans = Math.Min(ans,
exit[end] -
entrance[start]);
}
// Return answer
return ans >= int.MaxValue ?
-1 : ans;
}
static int upper_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
static int lowerBound(List<int> vec,
int low, int high,
int element)
{
int [] array = new int[vec.Count];
int k = 0;
foreach(int val in vec)
{
array[k] = val;
k++;
}
// vec.Clear();
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > array[middle])
{
low = middle + 1;
}
else
{
high = middle;
}
}
return low;
}
// Driver Code
public static void Main(String[] args)
{
// Stores interval of meeting
int [,]meeting = { { 15, 19 },
{ 5, 10 },
{ 7, 25 } };
// Stores entrance timings
int []entrance = { 4, 13, 25, 2 };
// Stores exit timings
exit.Add(10);
exit.Add(25);
// Stores total count of
// meetings
int n = meeting.GetLength(0);
// Stores total entrance
// timings
int m = entrance.Length;
// Stores total exit
// timings
int p = exit.Count;
// Minimum time
Console.Write(minTime(meeting, n,
entrance, m,
p) + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
let exit = [];
// Function to find the
// minimum time to attend
// exactly one meeting
function minTime(meeting, n, entrance, m, p)
{
// Stores minimum time to attend
// exactly one meeting
let ans = Number.MAX_VALUE;
// Sort entrance[] array
(entrance).sort(function(a, b){return a - b;});
// Sort exit[] time
(exit).sort(function(a, b){return a - b;});
// Traverse meeting[][]
for(let i = 0; i < n; i++)
{
// Stores start time of
// current meeting
let u = meeting[i][0];
// Stores end time of
// current meeting
let v = meeting[i][1];
// Find just greater value of
// u in entrance[]
let it1 = upper_bound(entrance, 0,
entrance.length, u);
// Find just greater or equal
// value of u in entrance[]
let it2 = lowerBound(exit, 0,
exit.length, v);
// System.out.println(exit.size());
// Stores enter time to attend
// the current meeting
let start = it1 - 1;
// Stores exist time after
// attending the meeting
let end = it2;
// Update start lies in range [0, m -1]
// and end lies in the range [0, p - 1]
if (start >= 0 && start < m &&
end >= 0 && end < p)
// Update ans
ans = Math.min(ans,
exit[end] -
entrance[start]);
}
// Return answer
return ans >= Number.MAX_VALUE ?
-1 : ans;
}
function upper_bound(a, low, high, element)
{
while(low < high)
{
let middle = low +
Math.floor((high - low) / 2);
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
function lowerBound(vec, low, high, element)
{
let array = new Array(vec.length);
let k = 0;
for(let val = 0; val < vec.length; val++)
{
array[k] = vec[val];
k++;
}
// vec.clear();
while (low < high)
{
let middle = low +
Math.floor((high - low) / 2);
if (element > array[middle])
{
low = middle + 1;
}
else
{
high = middle;
}
}
return low;
}
// Driver Code
// Stores interval of meeting
let meeting = [ [ 15, 19 ],
[ 5, 10 ],
[ 7, 25 ] ];
// Stores entrance timings
let entrance = [ 4, 13, 25, 2 ];
// Stores exit timings
exit.push(10);
exit.push(25);
// Stores total count of
// meetings
let n = meeting.length;
// Stores total entrance
// timings
let m = entrance.length;
// Stores total exit
// timings
let p = exit.length;
// Minimum time
document.write(minTime(meeting, n, entrance,
m, p) + "<br>");
// This code is contributed by unknown2108
</script>
Producción:
6
Complejidad de tiempo: O(N * max(logP, logM)) donde M y P son las longitudes de las arrays de entrada[] y de existencia[].
Espacio Auxiliar: O(1)