Максимальное увеличение количества работ, которые могут быть выполнены при заданном ограничении

Опубликовано: 1 Января, 2022

Учитывая целое число N, обозначающее количество заданий, и матрицу range [], состоящую из диапазона [день начала, день окончания] для каждого задания, в рамках которого оно должно быть выполнено, задача состоит в том, чтобы найти максимально возможные задания, которые могут быть выполнены.
Примеры:

Input: N = 5, Ranges = {{1, 5}, {1, 5}, {1, 5}, {2, 3}, {2, 3}} 
Output: 5 
Explanation: Job 1 on day 1, Job 4 on day 2, Job 5 on day 3, Job 2 on day 4, Job 3 on day 5

Input: N=6, Ranges = {{1, 3}, {1, 3}, {2, 3}, {2, 3}, {1, 4}, {2, 5}} 
Output: 5 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: указанная выше проблема может быть решена с помощью очереди приоритетов. Следуйте инструкциям ниже, чтобы решить проблемы:

  • Найдите минимальный и максимальный день в ассортименте вакансий.
  • Отсортируйте все задания в порядке возрастания дня начала .
  • Итерируйте от минимального к максимальному дню и для каждого i- го дня выберите задание с наименьшим днем окончания, которое может быть выполнено в этот день.
  • Для выполнения вышеуказанного шага поддерживайте минимальную кучу и каждый i- й день вставляйте задания, которые могут быть выполнены в этот день, в минимальную кучу, отсортированную по дню окончания . Если какое-либо задание может быть завершено в i- й день, рассмотрите задание с самым низким днем завершения и увеличьте количество выполненных заданий.
  • Повторите этот процесс для всех дней и, наконец, распечатайте количество выполненных заданий.

Ниже представлена реализация описанного выше подхода:

C ++

// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maxiumum
// 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 Program to implement the
// above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find maxiumum
// 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 maxiumum
# 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 maxiumum
// 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.
Выход:
 5

Сложность времени: O (Xlog (N)), где X - разница между максимальным и минимальным днем, а N - количество заданий.
Вспомогательное пространство: O (N 2 )

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022