Compruebe si la CPU procesará las requests dadas con éxito o no

Dada una capacidad entera , el número máximo de procesos manejados por una CPU en un momento dado y una solicitud de array 2-D [][] , cada solicitud tiene tres parámetros: 

• una serie de procesos que requieren CPU,
• hora de inicio,
• tiempo de finalización.

La tarea es verificar si la CPU atenderá todas las requests con éxito o no. En caso afirmativo, devuelva VERDADERO, de lo contrario, FALSO. La hora de inicio de la CPU es 0 inicialmente.

Ejemplos: 

Entrada: solicitud [] [] = {{2, 1, 5}, {3, 3, 7}}, capacidad = 4
Salida: falso
Explicación: la primera solicitud dice que 2 procesos necesitan CPU en el tiempo = 1 y se liberarán a la hora=5. Proceso de mantenimiento de CPU 2 a la vez = 1. Llega la segunda solicitud y le pide a la CPU que atienda 3 procesos más en el tiempo = 3 al tiempo = 7. En el momento = 3, la CPU está ocupada con la solicitud 1 y, por lo tanto, no puede atender la solicitud 2. Entonces, devuelve FALSO.

Entrada: solicitud[][] = {{2, 1, 5}, {3, 3, 7}}, capacidad = 5
Salida: verdadero

Enfoque : la idea es realizar un seguimiento de la utilización de la CPU en cada momento. Si la utilización de la CPU cruza su límite máximo, detenga el programa con el retorno FALSO. Sea curr el número de procesos actualmente en la CPU. Entonces inicialmente curr = 0 para request[i]

• a partir dei tiempo curr se incrementará en numProcessi
• en el tiempo toi curr se reducirá en numProcessi

en cualquier momento, si curr>capacity , simplemente devuelve falso. Siga los pasos a continuación para resolver el problema:

• Inicializa un vector del par v[].
• Itere sobre el rango [0, request.size()) usando la variable i y realice las siguientes tareas:
  • Empuje el par {request[i][1], request[i][0]} al vector v[].
  • Empuje el par {request[i][2], -request[i][0]} al vector v[].
• Ordenar el vector v[].
• Inicialice la variable curr como 0.
• Itere sobre el rango [0, v.size()) usando la variable i y realice las siguientes tareas:
  • Agregue v[i].segundo a la variable curr.
  • Si curr es mayor que la capacidad , devuelve falso.
• Después de realizar los pasos anteriores, devuelva verdadero como respuesta.

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

// C++ Program for the above approach
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
// Function to check whether all requests
// can be fulfilled or not
bool cpuAllocation(vector<vector<int> >& request,
                   int capacity)
{
    vector<pair<int, int> > v;
 
    for (int i = 0; i < request.size(); i++) {
 
        // Pushing fromi,
        // numPassengersi
        v.push_back({ request[i][1],
                      request[i][0] });
 
        // Pushing toi,
        // -numPassengersi
        v.push_back({ request[i][2],
                      -request[i][0] });
    }
 
    sort(v.begin(), v.end());
 
    int curr = 0;
 
    for (int i = 0; i < v.size(); i++) {
        curr += v[i].second;
 
        if (curr > capacity)
            return false;
    }
 
    return true;
}
 
// Driver Code
int main()
{
 
    vector<vector<int> > request{ { 2, 1, 5 },
                                  { 3, 3, 7 } };
    int capacity = 5;
    bool res = cpuAllocation(request, capacity);
    if (res == true)
        cout << "TRUE";
    else
        cout << "FALSE";
 
    return 0;
}

// Java Program for the above approach
 
import java.util.*;
 
class GFG {
  static class pair implements Comparable<pair> {
    int first, second;
 
    pair(int s, int e) {
      first = s;
      second = e;
    }
 
    // Function to sort the vector elements
    // ascending for first element
    // and if first element equal
    // then descending for second element
    public int compareTo(pair a) {
 
      return this.first > a.first ? 1 : 0;
    }
 
  }
 
  // Function to check whether all requests
  // can be fulfilled or not
  static boolean cpuAllocation(int[][] request, int capacity) {
    Vector<pair> v = new Vector<>();
 
    for (int i = 0; i < request.length; i++) {
 
      // Pushing fromi,
      // numPassengersi
      v.add(new pair(request[i][1], request[i][0]));
 
      // Pushing toi,
      // -numPassengersi
      v.add(new pair(request[i][2], -request[i][0]));
    }
 
    Collections.sort(v);
 
    int curr = 0;
 
    for (int i = 0; i < v.size(); i++) {
      curr += v.get(i).second;
 
      if (curr > capacity)
        return false;
    }
 
    return true;
  }
 
  // Driver Code
  public static void main(String[] args) {
 
    int[][] request = { { 2, 1, 5 }, { 3, 3, 7 } };
    int capacity = 5;
    boolean res = cpuAllocation(request, capacity);
    if (res == true)
      System.out.print("TRUE");
    else
      System.out.print("FALSE");
 
  }
}
 
// This code is contributed by 29AjayKumar

# Python Program for the above approach
class pair:
    def __init__(self, s, e):
        self.first = s
        self.second = e
 
# Function to check whether all requests
# can be fulfilled or not
def cpuAllocation(request, capacity):
    v = []
 
    for i in range(len(request)):
        # Pushing fromi,
        # numPassengersi
        v.append(pair(request[i][1], request[i][0]))
 
        # Pushing toi,
        # -numPassengersi
        v.append(pair(request[i][2], -request[i][0]))
 
    v.sort(key=lambda x: (x.first, -x.second))
 
    curr = 0
 
    for i in range(len(v)):
        curr += v[i].second
 
        if (curr > capacity):
            return False
 
    return True
 
# Driver Code
request = [[2, 1, 5], [3, 3, 7]]
capacity = 5
res = cpuAllocation(request, capacity)
if (res == True):
    print("TRUE")
else:
    print("FALSE")
 
# This code is contributed by Lovely Jain

// C# Program for the above approach
//include <algorithm>
 
//include <vector>
using System;
using System.Collections.Generic;
 
public class GFG {
  class pair : IComparable<pair>
  {
    public int first, second;
    public pair(int first, int second)
    {
      this.first = first;
      this.second = second;
    }
    public int CompareTo(pair p)
    {
      return this.first > p.first ? 1 : 0;
    }
  }
 
  // Function to check whether all requests
  // can be fulfilled or not
  static bool cpuAllocation(int[,] request, int capacity) {
    List<pair> v = new List<pair>();
 
    for (int i = 0; i < request.GetLength(0); i++) {
 
      // Pushing fromi,
      // numPassengersi
      v.Add(new pair(request[i,1], request[i,0]));
 
      // Pushing toi,
      // -numPassengersi
      v.Add(new pair(request[i,2], -request[i,0]));
    }
 
    v.Sort();
 
    int curr = 0;
 
    for (int i = 0; i < v.Count; i++) {
      curr += v[i].second;
 
      if (curr > capacity)
        return false;
    }
 
    return true;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    int[,] request = { { 2, 1, 5 }, { 3, 3, 7 } };
    int capacity = 5;
    bool res = cpuAllocation(request, capacity);
    if (res == true)
      Console.Write("TRUE");
    else
      Console.Write("FALSE");
 
  }
}
 
// This code is contributed by shikhasingrajput

<script>
// Javascript Program for the above approach
 
// Function to check whether all requests
// can be fulfilled or not
function cpuAllocation(request, capacity)
{
  let v = [];
 
  for (let i = 0; i < request.length; i++)
  {
 
    // Pushing fromi,
    // numPassengersi
    v.push([request[i][1], request[i][0]]);
 
    // Pushing toi,
    // -numPassengersi
    v.push([request[i][2], -request[i][0]]);
  }
 
  v.sort((a, b) => a[0] - b[0])
  curr = 0;
 
  for (let i = 0; i < v.length; i++) {
    curr += v[i][1];
 
    if (curr > capacity)
      return false;
  }
 
  return true;
}
 
// Driver Code
let request = [[2, 1, 5], [3, 3, 7]]
let capacity = 5;
let res = cpuAllocation(request, capacity);
if (res == true)
  document.write("TRUE");
else
  document.write("FALSE");
   
  // This code is contributed by gfgking.
</script>

TRUE

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)