Given an array of jobs with different time requirements, where each job consists of start time, end time and CPU load. The task is to find the maximum CPU load at any time if all jobs are running on the same machine.
Ejemplos:
Entrada: trabajos[] = {{1, 4, 3}, {2, 5, 4}, {7, 9, 6}}
Salida: 7
Explicación:
En los trabajos anteriores, hay dos trabajos que se superponen.
Es decir, el trabajo [1, 4, 3] y [2, 5, 4] se superponen durante el período de tiempo en [2, 4].
Por lo tanto, la carga máxima de la CPU en este instante será máxima (3 + 4 = 7).Entrada: trabajos[] = {{6, 7, 10}, {2, 4, 11}, {8, 12, 15}}
Salida: 15
Explicación:
Dado que no hay trabajos que se superpongan.
La carga máxima de la CPU será: max(10, 11, 15) = 15
Este problema es generalmente la aplicación de los intervalos de fusión .
Enfoque: la idea es mantener un montón mínimo para los trabajos en función de sus tiempos de finalización. Luego, para cada instancia, encuentre los trabajos que están completos y elimínelos del Min-heap. Es decir, compruebe que la hora de finalización de los trabajos en el montón mínimo haya finalizado antes de la hora de inicio del trabajo actual. Además, en cada instancia, encuentre la carga máxima de CPU en la máquina tomando la suma de todos los trabajos que están presentes en el montón mínimo.
Por ejemplo:
Given Jobs be {{1, 4, 3}, {2, 5, 4}, {7, 9, 6}}
Min-Heap - {}
Instance 1:
The job {1, 4, 3} is inserted into the min-heap
Min-Heap - {{1, 4, 3}},
Total CPU Load = 3
Instance 2:
The job {2, 5, 4} is inserted into the min-heap.
While the job {1, 4, 3} is still in the CPU,
because end-time of Job 1 is greater than
the start time of the new job {2, 5, 4}.
Min-Heap - {{1, 4, 3}, {2, 5, 4}}
Total CPU Load = 4 + 3 = 7
Instance 3:
The job {7, 9, 6} is inserted into the min-heap.
After popping up all the other jobs because their
end time is less than the start time of the new job
Min Heap - {7, 9, 6}
Total CPU Load = 6
Maximum CPU Load = max(3, 7, 6) = 7
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum CPU Load from the given
// lists of the jobs
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Blueprint of the job
class Job {
public:
int start = 0;
int end = 0;
int cpuLoad = 0;
// Constructor function for
// the CPU Job
Job(int start, int end, int cpuLoad)
{
this->start = start;
this->end = end;
this->cpuLoad = cpuLoad;
}
};
class MaximumCPULoad {
// Structure to compare two
// CPU Jobs by their end time
public:
struct endCompare {
bool operator()(const Job& x, const Job& y)
{
return x.end > y.end;
}
};
// Function to find the maximum
// CPU Load at any instance of
// the time for given jobs
static int findMaxCPULoad(vector<Job>& jobs)
{
// Condition when there are
// no jobs then CPU Load is 0
if (jobs.empty()) {
return 0;
}
// Sorting all the jobs
// by their start time
sort(jobs.begin(), jobs.end(),
[](const Job& a, const Job& b) {
return a.start < b.start;
});
int maxCPULoad = 0;
int currentCPULoad = 0;
// Min-heap implemented using the
// help of the priority queue
priority_queue<Job, vector<Job>, endCompare>
minHeap;
// Loop to iterate over all the
// jobs from the given list
for (auto job : jobs) {
// Loop to remove all jobs from
// the heap which is ended
while (!minHeap.empty()
&& job.start > minHeap.top().end) {
currentCPULoad -= minHeap.top().cpuLoad;
minHeap.pop();
}
// Add the current Job to CPU
minHeap.push(job);
currentCPULoad += job.cpuLoad;
maxCPULoad = max(maxCPULoad, currentCPULoad);
}
return maxCPULoad;
}
};
// Driver Code
int main(int argc, char* argv[])
{
vector<Job> input
= { { 1, 4, 3 }, { 7, 9, 6 }, { 2, 5, 4 } };
cout << "Maximum CPU load at any time: "
<< MaximumCPULoad::findMaxCPULoad(input) << endl;
}
Python3
# Python implementation to find the
# maximum CPU Load from the given
# lists of the jobs
from heapq import *
# Blueprint of the job
class job:
# Constructor of the Job
def __init__(self, start,
end, cpu_load):
self.start = start
self.end = end
self.cpu_load = cpu_load
# Operator overloading for the
# Object that is Job
def __lt__(self, other):
# min heap based on job.end
return self.end < other.end
# Function to find the maximum
# CPU Load for the given list of jobs
def find_max_cpu_load(jobs):
# Sort the jobs by start time
jobs.sort(key=lambda x: x.start)
max_cpu_load, current_cpu_load = 0, 0
# Min-Heap
min_heap = []
# Loop to iterate over the list
# of the jobs given for the CPU
for j in jobs:
# Remove all the jobs from
# the min-heap which ended
while(len(min_heap) > 0 and
j.start >= min_heap[0].end):
current_cpu_load -= min_heap[0].cpu_load
heappop(min_heap)
# Add the current job
# into min_heap
heappush(min_heap, j)
current_cpu_load += j.cpu_load
max_cpu_load = max(max_cpu_load,
current_cpu_load)
return max_cpu_load
# Driver Code
if __name__ == "__main__":
jobs = [job(1, 4, 3), job(2, 5, 4),
job(7, 9, 6)]
print("Maximum CPU load at any time: " +
str(find_max_cpu_load(jobs)))
Maximum CPU load at any time: 7
Análisis de rendimiento:
- Complejidad del tiempo: O(N*logN)
- Espacio Auxiliar: O(N)
La idea es sencilla. Hemos supuesto n intervalos, por lo que tenemos 2n puntos finales (aquí punto final es el final de un intervalo y su valor es el tiempo asociado a él). Podemos tomar un punto final y combinarlo con su valor de carga asociado y con una bandera que indica si es un punto inicial o final de un intervalo. Luego, podemos ordenar los puntos finales en orden creciente (si hay un empate en el valor de los puntos finales, romperemos el empate colocando el punto final que comienza en primer lugar en comparación con el punto final que está terminando; si ambos puntos finales son comenzando o terminando entonces desempataremos arbitrariamente).
Después de ordenar, procederemos a través de los puntos finales usando for loop. Y si tenemos un punto final que es el punto de inicio de un intervalo, agregaremos el valor de carga asociado con él en una variable, por ejemplo, contar. También tomaremos el máximo de los valores de conteo y lo almacenaremos en una variable llamada resultado.
Pero cuando obtenemos un punto final que está finalizando, disminuiremos el valor de carga asociado con él del conteo.
Al final, devolveremos el resultado.
Tomemos un ejemplo: supongamos que los trabajos son {1, 4, 3}, {2, 5, 4}, {7, 9, 6}.
nuestros puntos finales ordenados serán 1 (inicio), 2 (inicio), 4 (final), 5 (final), 7 (inicio), 9 (final) .
y las cargas correspondientes serán 3, 4, 3, 4, 6, 6.
empezar a atravesar los puntos finales:
entonces, después de atravesar el primer punto final, que es 1 (inicio), tenemos count+=3 (aquí 3 es la carga asociada), entonces count =3. Dado que el 1 es el punto de partida, actualizaremos el resultado. Entonces result=max(result,count) entonces, result=3.
Después de atravesar 2 (inicio) tenemos cuenta+=4, entonces cuenta=7, resultado=máximo(resultado,cuenta)=7.
Después de atravesar 4 (final) tenemos count-=3 (hemos restado porque es el punto final), entonces count=4. el resultado no se actualizará ya que estamos disminuyendo el conteo.
Después de atravesar 5 (final) tenemos count-=4 así que count=0.
Después de atravesar 7 (inicio) tenemos cuenta+=6 entonces cuenta=6, resultado=máximo(resultado,cuenta)=7.
Después de atravesar 9 (final) tenemos count-=6 así que count=0.
Nuestro resultado será 7.
C++14
// C++ implementation to find the
// maximum CPU Load from the given array of jobs
#include <bits/stdc++.h>
using namespace std;
// the job struct will have s(starting time) , e(ending time) , load(cpu load)
struct Job {
int s, e, load;
};
// endpoint struct will have val(the time associated with the endpoint),
// load(cpu load associated with the endpoint),
// a flag isStart which will tell if the endpoint is starting or ending point of
// an interval
struct Endpoint {
int val, load;
bool isStart;
};
// custom comparator function which is used by the c++ sort stl
bool comp(const Endpoint& a, const Endpoint& b) {
if (a.val != b.val)
return a.val < b.val;
return a.isStart == true && b.isStart == false;
}
//function to find maximum cpu load
int maxCpuLoad(vector<Job> v)
{
int count = 0; // count will contain the count of current loads
int result = 0; // result will contain maximum of all counts
// this data array will contain all the endpoints combined with their load values
// and flags telling whether they are starting or ending point
vector<Endpoint> data;
for (int i = 0; i < v.size(); i++) {
data.emplace_back(Endpoint{ v[i].s, v[i].load, true});
data.emplace_back(Endpoint{ v[i].e, v[i].load, false});
}
sort(data.begin(), data.end(), comp);
for (int i = 0; i < data.size(); i++) {
if (data[i].isStart == true) {
count += data[i].load;
result = max(result, count);
}
else
count -= data[i].load;
}
return result;
}
//Driver code to test maxCpuLoad function
int main() {
vector<Job> v = {
{6, 7, 10},
{2, 4, 11},
{8, 12, 15}
};
cout << maxCpuLoad(v);
return 0;
}
// this code is contributed by Mohit Puri
Python3
# Python3 implementation to find the # maximum CPU Load from the given array of jobs # the job struct will have s(starting time) , e(ending time) , load(cpu load) class Job: def __init__(self,s,e,l) -> None: self.s =s; self.e =e; self.load = l # endpoint will have val(the time associated with the endpoint), # load(cpu load associated with the endpoint), # a flag isStart which will tell if the endpoints starting or ending point # an interval class Endpoint: def __init__(self, v=0, l=0, isStart=False) -> None: self.val = v self.load = l self.isStart = isStart def __lt__(self, other): if self.val != other.val: return self.val < other.val return self.isStart == True and other.isStart == False # function to find maximum cpu load def maxCpuLoad(v): count = 0 # count will contain the count of current loads result = 0 # result will contain maximum of all counts # this data array will contain all the endpoints combined with their load values # and flags telling whether they are starting or ending point data = [] for i in range(len(v)): data.append(Endpoint(v[i].s, v[i].load, True)) data.append(Endpoint(v[i].e, v[i].load, False)) data.sort() for i in range(len(data)): if data[i].isStart == True: count += data[i].load result = max(result, count) else: count -= data[i].load return result # Driver code to test maxCpuLoad function if __name__ == "__main__": v = [Job(6, 7, 10), Job(2, 4, 11), Job(8, 12, 15)] print(maxCpuLoad(v))
Javascript
<script>
// JavaScript implementation to find the
// maximum CPU Load from the given array of jobs
// the job struct will have s(starting time) , e(ending time) , load(cpu load)
class Job{
constructor(s,e,l){
this.s = s; this.e = e; this.load = l
}
}
// endpoint will have val(the time associated with the endpoint),
// load(cpu load associated with the endpoint),
// a flag isStart which will tell if the endpoints starting or ending point
// an interval
class Endpoint{
constructor(v = 0, l = 0, isStart = false){
this.val = v
this.load = l
this.isStart = isStart
}
}
function comp(a, b) {
if (a.val != b.val)
return a.val - b.val;
return a.isStart == true && b.isStart == false;
}
// function to find maximum cpu load
function maxCpuLoad(v){
let count = 0 // count will contain the count of current loads
let result = 0 // result will contain maximum of all counts
// this data array will contain all the endpoints combined with their load values
// and flags telling whether they are starting or ending point
let data = []
for(let i = 0; i < v.length; i++){
data.push(new Endpoint(v[i].s, v[i].load, true))
data.push(new Endpoint(v[i].e, v[i].load, false))
}
data.sort(comp)
for(let i = 0; i < data.length; i++)
{
if(data[i].isStart == true){
count += data[i].load
result = Math.max(result, count)
}
else
count -= data[i].load
}
return result
}
// Driver code to test maxCpuLoad function
let v = [new Job(6, 7, 10), new Job(2, 4, 11), new Job(8, 12, 15)]
document.write(maxCpuLoad(v),"</br>")
// This code is contributed by shinjanpatra
</script>
15
Complejidad de tiempo: O (nlogn) para ordenar la array de datos.
Complejidad espacial: O(n) que es el tamaño de la array de datos