Dados los tiempos de clase N , con su hora de inicio y hora de finalización (ambas inclusive), la tarea es encontrar el número mínimo de salas necesarias para llevar a cabo todas las clases de modo que una sola sala pueda usarse para una sola conferencia en un momento dado. Tenga en cuenta que el tiempo máximo de finalización puede ser 10 5 .
Ejemplos:
Entrada: conferencias[][] = {{0, 5}, {1, 2}, {1, 10}}
Salida: 3
Todas las conferencias deben llevarse a cabo en salas diferentes porque
en la instancia de tiempo 1 todas las conferencias están en curso.
Entrada: conferencias[][] = {{0, 5}, {1, 2}, {6, 10}}
Salida: 2
Acercarse:
- Suponiendo que el tiempo T comienza con 0. La tarea es encontrar el número máximo de conferencias que están en curso en un momento determinado. Esto dará el número mínimo de salas necesarias para programar todas las conferencias.
- Para encontrar el número de conferencias en curso en cualquier instancia de tiempo. Mantenga un prefix_sum[] que almacenará el número de conferencias en curso en cualquier instancia de tiempo t. Para cualquier conferencia con tiempos entre [s, t], haga prefix_sum[s]++ y prefix_sum[t + 1]–.
- Posteriormente, la suma acumulativa de esta array de prefijos dará el recuento de conferencias en cualquier momento.
- El valor máximo para cualquier instante de tiempo t en la array es el número mínimo de salas requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
// Function to return the minimum
// number of halls required
int minHalls(int lectures[][2], int n)
{
// Array to store the number of
// lectures ongoing at time t
int prefix_sum[MAX] = { 0 };
// For every lecture increment start
// point s decrement (end point + 1)
for (int i = 0; i < n; i++) {
prefix_sum[lectures[i][0]]++;
prefix_sum[lectures[i][1] + 1]--;
}
int ans = prefix_sum[0];
// Perform prefix sum and update
// the ans to maximum
for (int i = 1; i < MAX; i++) {
prefix_sum[i] += prefix_sum[i - 1];
ans = max(ans, prefix_sum[i]);
}
return ans;
}
// Driver code
int main()
{
int lectures[][2] = { { 0, 5 },
{ 1, 2 },
{ 1, 10 } };
int n = sizeof(lectures) / sizeof(lectures[0]);
cout << minHalls(lectures, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 100001;
// Function to return the minimum
// number of halls required
static int minHalls(int lectures[][], int n)
{
// Array to store the number of
// lectures ongoing at time t
int []prefix_sum = new int[MAX];
// For every lecture increment start
// point s decrement (end point + 1)
for (int i = 0; i < n; i++)
{
prefix_sum[lectures[i][0]]++;
prefix_sum[lectures[i][1] + 1]--;
}
int ans = prefix_sum[0];
// Perform prefix sum and update
// the ans to maximum
for (int i = 1; i < MAX; i++)
{
prefix_sum[i] += prefix_sum[i - 1];
ans = Math.max(ans, prefix_sum[i]);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int lectures[][] = {{ 0, 5 },
{ 1, 2 },
{ 1, 10 }};
int n = lectures.length;
System.out.println(minHalls(lectures, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach MAX = 100001 # Function to return the minimum # number of halls required def minHalls(lectures, n) : # Array to store the number of # lectures ongoing at time t prefix_sum = [0] * MAX; # For every lecture increment start # point s decrement (end point + 1) for i in range(n) : prefix_sum[lectures[i][0]] += 1; prefix_sum[lectures[i][1] + 1] -= 1; ans = prefix_sum[0]; # Perform prefix sum and update # the ans to maximum for i in range(1, MAX) : prefix_sum[i] += prefix_sum[i - 1]; ans = max(ans, prefix_sum[i]); return ans; # Driver code if __name__ == "__main__" : lectures = [[ 0, 5 ], [ 1, 2 ], [ 1, 10 ]]; n = len(lectures); print(minHalls(lectures, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 100001;
// Function to return the minimum
// number of halls required
static int minHalls(int [,]lectures, int n)
{
// Array to store the number of
// lectures ongoing at time t
int []prefix_sum = new int[MAX];
// For every lecture increment start
// point s decrement (end point + 1)
for (int i = 0; i < n; i++)
{
prefix_sum[lectures[i,0]]++;
prefix_sum[lectures[i,1] + 1]--;
}
int ans = prefix_sum[0];
// Perform prefix sum and update
// the ans to maximum
for (int i = 1; i < MAX; i++)
{
prefix_sum[i] += prefix_sum[i - 1];
ans = Math.Max(ans, prefix_sum[i]);
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int [,]lectures = {{ 0, 5 },
{ 1, 2 },
{ 1, 10 }};
int n = lectures.GetLength(0);
Console.WriteLine(minHalls(lectures, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
const MAX = 100001;
// Function to return the minimum
// number of halls required
function minHalls(lectures, n)
{
// Array to store the number of
// lectures ongoing at time t
let prefix_sum = new Uint8Array(MAX);
// For every lecture increment start
// point s decrement (end point + 1)
for (let i = 0; i < n; i++) {
prefix_sum[lectures[i][0]]++;
prefix_sum[lectures[i][1] + 1]--;
}
let ans = prefix_sum[0];
// Perform prefix sum and update
// the ans to maximum
for (let i = 1; i < MAX; i++) {
prefix_sum[i] += prefix_sum[i - 1];
ans = Math.max(ans, prefix_sum[i]);
}
return ans;
}
// Driver code
let lectures = [ [ 0, 5 ],
[ 1, 2 ],
[ 1, 10 ] ];
let n = lectures.length;
document.write(minHalls(lectures, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
3