Dado un número entero N que denota el número de trabajos y una array de rangos[] que consta de un rango [día de inicio, día de finalización] para cada trabajo dentro del cual debe completarse, la tarea es encontrar el máximo de trabajos posibles que se pueden completar.
Ejemplos:
Entrada: N = 5, Rangos = {{1, 5}, {1, 5}, {1, 5}, {2, 3}, {2, 3}}
Salida: 5
Explicación: Trabajo 1 el día 1, Trabajo 4 el día 2, Trabajo 5 el día 3, Trabajo 2 el día 4, Trabajo 3 el día 5Entrada: N=6, Rangos = {{1, 3}, {1, 3}, {2, 3}, {2, 3}, {1, 4}, {2, 5}}
Salida: 5
Enfoque: el problema anterior se puede resolver utilizando una cola de prioridad . Siga los pasos a continuación para resolver los problemas:
- Encuentre el día mínimo y máximo en el rango de trabajos.
- Ordene todos los trabajos en orden creciente del día de inicio .
- Iterar desde el día mínimo hasta el día máximo, y para cada i -ésimo día, seleccionar el trabajo que tenga el menor día de finalización que se pueda completar ese día.
- Para realizar el paso anterior, mantenga un Montón mínimo y, cada día i , inserte los trabajos que se pueden completar ese día en el Montón mínimo ordenados por día de finalización . Si algún trabajo puede completarse en el i -ésimo día, considere el que tenga el día de finalización más bajo y aumente el recuento de trabajos completados.
- Repita este proceso para todos los días y finalmente imprima el conteo de trabajos completados.
A continuación se muestra una implementación del enfoque anterior:
C++
// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum
// number of jobs
int find_maximum_jobs(
int N,
vector<pair<int, int> > ranges)
{
// Min Heap
priority_queue<int, vector<int>,
greater<int> >
queue;
// Sort ranges by start day
sort(ranges.begin(), ranges.end());
// Stores the minimum and maximum
// day in the ranges
int min_day = ranges[0].first;
int max_day = 0;
for (int i = 0; i < N; i++)
max_day
= max(max_day,
ranges[i].second);
int index = 0, count_jobs = 0;
// Iterating from min_day to max_day
for (int i = min_day; i <= max_day; i++) {
// Insert the end day of the jobs
// which can be completed on
// i-th day in a priority queue
while (index < ranges.size()
&& ranges[index].first <= i) {
queue.push(ranges[index].second);
index++;
}
// Pop all jobs whose end day
// is less than current day
while (!queue.empty()
&& queue.top() < i)
queue.pop();
// If queue is empty, no job
// can be completed on
// the i-th day
if (queue.empty())
continue;
// Increment the count of
// jobs completed
count_jobs++;
// Pop the job with
// least end day
queue.pop();
}
// Return the jobs
// on the last day
return count_jobs;
}
// Driver Code
int main()
{
int N = 5;
vector<pair<int, int> > ranges;
ranges.push_back({ 1, 5 });
ranges.push_back({ 1, 5 });
ranges.push_back({ 1, 5 });
ranges.push_back({ 2, 3 });
ranges.push_back({ 2, 3 });
cout << find_maximum_jobs(N, ranges);
}
Java
// Java Program to implement the
// above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find maximum
// number of jobs
static int find_maximum_jobs(int N, ArrayList<ArrayList<Integer>> ranges)
{
// Min Heap
ArrayList<Integer> queue = new ArrayList<Integer>();
// Sort ranges by start day
Collections.sort(ranges, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
return o1.get(0).compareTo(o2.get(0));
}
});
// Stores the minimum and maximum
// day in the ranges
int min_day = ranges.get(0).get(0);
int max_day = 0;
for (int i = 0; i < N; i++)
max_day = Math.max(max_day, ranges.get(i).get(1));
int index = 0, count_jobs = 0;
// Iterating from min_day to max_day
for (int i = min_day; i <= max_day; i++)
{
// Insert the end day of the jobs
// which can be completed on
// i-th day in a priority queue
while (index < ranges.size() && ranges.get(index).get(0) <= i)
{
queue.add(ranges.get(index).get(1));
index++;
}
Collections.sort(queue);
// Pop all jobs whose end day
// is less than current day
while (queue.size() > 0 && queue.get(0) < i)
queue.remove(0);
// If queue is empty, no job
// can be completed on
// the i-th day
if (queue.size() == 0)
continue;
// Increment the count of
// jobs completed
count_jobs++;
// Pop the job with
// least end day
queue.remove(0);
}
// Return the jobs
// on the last day
return count_jobs;
}
// Driver code
public static void main (String[] args) {
int N = 5;
ArrayList<ArrayList<Integer>> ranges = new ArrayList<ArrayList<Integer>>();
ranges.add(new ArrayList<Integer>(Arrays.asList(1, 5)));
ranges.add(new ArrayList<Integer>(Arrays.asList(1, 5)));
ranges.add(new ArrayList<Integer>(Arrays.asList(1, 5)));
ranges.add(new ArrayList<Integer>(Arrays.asList(2, 3)));
ranges.add(new ArrayList<Integer>(Arrays.asList(2, 3)));
System.out.println(find_maximum_jobs(N, ranges));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 Program to implement the # above approach # Function to find maximum # number of jobs def find_maximum_jobs(N, ranges) : # Min Heap queue = [] # Sort ranges by start day ranges.sort() # Stores the minimum and maximum # day in the ranges min_day = ranges[0][0] max_day = 0 for i in range(N) : max_day = max(max_day, ranges[i][1]) index, count_jobs = 0, 0 # Iterating from min_day to max_day for i in range(min_day, max_day + 1) : # Insert the end day of the jobs # which can be completed on # i-th day in a priority queue while (index < len(ranges) and ranges[index][0] <= i) : queue.append(ranges[index][1]) index += 1 queue.sort() # Pop all jobs whose end day # is less than current day while (len(queue) > 0 and queue[0] < i) : queue.pop(0) # If queue is empty, no job # can be completed on # the i-th day if (len(queue) == 0) : continue # Increment the count of # jobs completed count_jobs += 1 # Pop the job with # least end day queue.pop(0) # Return the jobs # on the last day return count_jobs # Driver code N = 5 ranges = [] ranges.append((1, 5)) ranges.append((1, 5)) ranges.append((1, 5)) ranges.append((2, 3)) ranges.append((2, 3)) print(find_maximum_jobs(N, ranges)) # This code is contributed by divyeshrabadiya07.
C#
// C# Program to implement the
// above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find maximum
// number of jobs
static int find_maximum_jobs(int N, List<Tuple<int, int>> ranges)
{
// Min Heap
List<int> queue = new List<int>();
// Sort ranges by start day
ranges.Sort();
// Stores the minimum and maximum
// day in the ranges
int min_day = ranges[0].Item1;
int max_day = 0;
for (int i = 0; i < N; i++)
max_day = Math.Max(max_day, ranges[i].Item2);
int index = 0, count_jobs = 0;
// Iterating from min_day to max_day
for (int i = min_day; i <= max_day; i++)
{
// Insert the end day of the jobs
// which can be completed on
// i-th day in a priority queue
while (index < ranges.Count && ranges[index].Item1 <= i)
{
queue.Add(ranges[index].Item2);
index++;
}
queue.Sort();
// Pop all jobs whose end day
// is less than current day
while (queue.Count > 0 && queue[0] < i)
queue.RemoveAt(0);
// If queue is empty, no job
// can be completed on
// the i-th day
if (queue.Count == 0)
continue;
// Increment the count of
// jobs completed
count_jobs++;
// Pop the job with
// least end day
queue.RemoveAt(0);
}
// Return the jobs
// on the last day
return count_jobs;
}
// Driver code
static void Main()
{
int N = 5;
List<Tuple<int, int>> ranges = new List<Tuple<int, int>>();
ranges.Add(new Tuple<int,int>(1, 5));
ranges.Add(new Tuple<int,int>(1, 5));
ranges.Add(new Tuple<int,int>(1, 5));
ranges.Add(new Tuple<int,int>(2, 3));
ranges.Add(new Tuple<int,int>(2, 3));
Console.Write(find_maximum_jobs(N, ranges));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// JavaScript program for the above approach
// Function to find maximum
// number of jobs
function find_maximum_jobs(N, ranges){
// Min Heap
let queue = []
// Sort ranges by start day
ranges.sort()
// Stores the minimum && maximum
// day in the ranges
let min_day = ranges[0][0]
let max_day = 0
for(let i = 0;i<N ; i++){
max_day = Math.max(max_day, ranges[i][1])
}
let index = 0, count_jobs = 0
// Iterating from min_day to max_day
for(let i = min_day;i< max_day + 1;i++) {
// Insert the end day of the jobs
// which can be completed on
// i-th day in a priority queue
while (index < ranges.length && ranges[index][0] <= i){
queue.push(ranges[index][1])
index += 1
}
queue.sort()
// Pop all jobs whose end day
// is less than current day
while (queue.length > 0 && queue[0] < i)
queue.shift()
// If queue is empty, no job
// can be completed on
// the i-th day
if (queue.length == 0)
continue
// Increment the count of
// jobs completed
count_jobs += 1
// Pop the job with
// least end day
queue.shift()
}
// Return the jobs
// on the last day
return count_jobs
}
// Driver code
let N = 5
let ranges = []
ranges.push([1, 5])
ranges.push([1, 5])
ranges.push([1, 5])
ranges.push([2, 3])
ranges.push([2, 3])
document.write(find_maximum_jobs(N, ranges))
// This code is contributed by shinjanpatra
</script>
Producción:
5
Complejidad Temporal: O(Xlog(N)), donde X es la diferencia entre el día máximo y mínimo y N es el número de trabajos.
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por Mayank Rana 1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA