Given an integer N denoting number of jobs and a matrix ranges[] consisting of a range [start day, end day] for each job within which it needs to be completed, the task is to find the maximum possible jobs that can be completed.
Examples:
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 5Input: N=6, Ranges = {{1, 3}, {1, 3}, {2, 3}, {2, 3}, {1, 4}, {2, 5}}
Output: 5
Approach: The above problem can be solved using a Priority Queue. Follow the steps below to solve the problems:
- Find the minimum and maximum day in the range of jobs.
- Sort all jobs in increasing order of start day.
- Iterate from the minimum to maximum day, and for every ith day, select the job having least end day which can be completed on that day.
- In order to perform the above step, maintain a Min Heap, and on every ith day, insert the jobs that can be completed on that day, into the Min Heap sorted by end day. If any job can completed on the ith day, consider the one with the lowest end day and increase the count of jobs completed.
- Repeat this process for all the days and finally print the count of jobs completed.
Below is an implementation of the above approach:
C++
// C++ Program to implement the// above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum// number of jobsint 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 Codeint 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 codeN = 5ranges = []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 codelet N = 5let 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> |
Output:
5
Time Complexity: O(Xlog(N)), where X is the difference between maximum and minimum day and N is the number of jobs.
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
