Dada una array bidimensional arr[][] de dimensiones N * 2 que contiene la hora de inicio y finalización de N reuniones en un día determinado. La tarea es imprimir una lista de intervalos de tiempo durante los cuales se puede realizar la mayor cantidad de reuniones simultáneas.
Ejemplos:
Entrada: arr[][] = {{100, 300}, {145, 215}, {200, 230}, {215, 300}, {215, 400}, {500, 600}, {600, 700} }
Salida: [215, 230]
Explicación:
Las 5 reuniones dadas se superponen en {215, 230}.Entrada: arr[][] = {{100, 200}, {50, 300}, {300, 400}}
Salida: [100, 200]
Enfoque: La idea es usar un Min-Heap para resolver este problema. A continuación se muestran los pasos:
- Ordene la array según la hora de inicio de las reuniones.
- Inicializar un min-heap .
- Inicialice las variables max_len , max_start y max_end para almacenar el tamaño máximo del montón mínimo, la hora de inicio y la hora de finalización de las reuniones simultáneas, respectivamente.
- Iterar sobre la array ordenada y seguir saltando desde min_heap hasta que arr[i][0] se vuelva más pequeño que los elementos de min_heap , es decir, saque todas las reuniones que tengan una hora de finalización menor que la hora de inicio de la reunión actual y presione arr[i] [1] en min_heap .
- Si el tamaño de min_heap supera max_len , actualice max_len = size(min_heap) , max_start = meeting[i][0] y max_end = min_heap_element.
- Devuelve el valor de max_start y max_end al final.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
bool cmp(vector<int> a,vector<int> b)
{
if(a[0] != b[0])
return a[0] < b[0];
return a[1] - b[1];
}
// Function to find time slot of
// maximum concurrent meeting
void maxConcurrentMeetingSlot(
vector<vector<int>> meetings)
{
// Sort array by
// start time of meeting
sort(meetings.begin(), meetings.end(), cmp);
// Declare Minheap
priority_queue<int, vector<int>,
greater<int>> pq;
// Insert first meeting end time
pq.push(meetings[0][1]);
// Initialize max_len,
// max_start and max_end
int max_len = 0, max_start = 0;
int max_end = 0;
// Traverse over sorted array
// to find required slot
for(auto k : meetings)
{
// Pop all meetings that end
// before current meeting
while (pq.size() > 0 &&
k[0] >= pq.top())
pq.pop();
// Push current meeting end time
pq.push(k[1]);
// Update max_len, max_start
// and max_end if size of
// queue is greater than max_len
if (pq.size() > max_len)
{
max_len = pq.size();
max_start = k[0];
max_end = pq.top();
}
}
// Print slot of maximum
// concurrent meeting
cout << max_start << " " << max_end;
}
// Driver Code
int main()
{
// Given array of meetings
vector<vector<int>> meetings = { { 100, 200 },
{ 50, 300 },
{ 300, 400 } };
// Function call
maxConcurrentMeetingSlot(meetings);
}
// This code is contributed by mohit kumar 29
Java
// Java implementation of the
// above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to find time slot of
// maximum concurrent meeting
static void maxConcurrentMeetingSlot(
int[][] meetings)
{
// Sort array by
// start time of meeting
Arrays.sort(meetings,
(a, b)
-> (a[0] != b[0])
? a[0] - b[0]
: a[1] - b[1]);
// Declare Minheap
PriorityQueue<Integer> pq
= new PriorityQueue<>();
// Insert first meeting end time
pq.add(meetings[0][1]);
// Initialize max_len,
// max_start and max_end
int max_len = 0, max_start = 0;
int max_end = 0;
// Traverse over sorted array
// to find required slot
for (int[] k : meetings) {
// Pop all meetings that end
// before current meeting
while (!pq.isEmpty()
&& k[0] >= pq.peek())
pq.poll();
// Push current meeting end time
pq.add(k[1]);
// Update max_len, max_start
// and max_end if size of
// queue is greater than max_len
if (pq.size() > max_len) {
max_len = pq.size();
max_start = k[0];
max_end = pq.peek();
}
}
// Print slot of maximum
// concurrent meeting
System.out.println(
max_start + " " + max_end);
}
// Driver Code
public static void main(String[] args)
{
// Given array of meetings
int meetings[][]
= { { 100, 200 },
{ 50, 300 },
{ 300, 400 } };
// Function Call
maxConcurrentMeetingSlot(meetings);
}
}
Python3
# Python implementation of the
# above approach
# Function to find time slot of
# maximum concurrent meeting
from functools import cmp_to_key
def mycmp(a, b):
return a[0] - b[0] if (a[0] != b[0]) else a[1] - b[1]
def maxConcurrentMeetingSlot(meetings):
# Sort array by
# start time of meeting
meetings.sort(key = cmp_to_key(mycmp))
# Declare Minheap
pq = []
# Insert first meeting end time
pq.append(meetings[0][1])
pq.sort()
# Initialize max_len,
# max_start and max_end
max_len,max_start,max_end = 0,0,0
# Traverse over sorted array
# to find required slot
for k in range(len(meetings)):
# Pop all meetings that end
# before current meeting
while (len(pq)!=0 and meetings[k][0] >= pq[0]):
pq.pop(0)
# Push current meeting end time
pq.append(meetings[k][1])
pq.sort()
# Update max_len, max_start
# and max_end if size of
# queue is greater than max_len
if (len(pq) > max_len):
max_len = len(pq)
max_start = meetings[k][0]
max_end = pq[0]
# Print slot of maximum
# concurrent meeting
print(f"{max_start} {max_end}")
# Driver Code
meetings = [[ 100, 200 ],[ 50, 300 ],[ 300, 400 ]]
# Function Call
maxConcurrentMeetingSlot(meetings)
# This code is contributed by shinjanpatra
Javascript
<script>
// Javascript implementation of the
// above approach
// Function to find time slot of
// maximum concurrent meeting
function maxConcurrentMeetingSlot(meetings)
{
// Sort array by
// start time of meeting
meetings.sort(function(a, b){return (a[0] != b[0])
? a[0] - b[0]
: a[1] - b[1]});
// Declare Minheap
let pq = [];
// Insert first meeting end time
pq.push(meetings[0][1]);
pq.sort(function(a,b){return a-b;});
// Initialize max_len,
// max_start and max_end
let max_len = 0, max_start = 0;
let max_end = 0;
// Traverse over sorted array
// to find required slot
for (let k=0;k< meetings.length;k++) {
// Pop all meetings that end
// before current meeting
while (pq.length!=0
&& meetings[k][0] >= pq[0])
pq.shift();
// Push current meeting end time
pq.push(meetings[k][1]);
pq.sort(function(a,b){return a-b;});
// Update max_len, max_start
// and max_end if size of
// queue is greater than max_len
if (pq.length > max_len) {
max_len = pq.length;
max_start = meetings[k][0];
max_end = pq[0];
}
}
// Print slot of maximum
// concurrent meeting
document.write(
max_start + " " + max_end+"<br>");
}
// Driver Code
let meetings
= [[ 100, 200 ],
[ 50, 300 ],
[ 300, 400 ]];
// Function Call
maxConcurrentMeetingSlot(meetings);
// This code is contributed by unknown2108
</script>
Producción:
100 200
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)