There are N jobs and the start and finish times of the jobs are given in arrays start[] and end[] respectively. Each job requires one laptop and laptops can’t be shared. Find the minimum number of laptops required given that you can give your laptop to someone else when you are not doing your job.
Examples:
Input: N = 3, start[] = {1, 2, 3}, end[] = {4, 4, 6}
Output: 3
Explanation: We can clearly see that everyone’s supposed to be doing their job at time 3. So, 3 laptops will be required at minimum.Input: N = 3, start[] = {1, 5, 2}, end[] = {2, 6, 3}
Output: 1
Explanation: All jobs can be done using 1 laptop only.
Approach: This can be solved with the following idea:
We need to determine the bare minimum of laptops needed to complete the task. If we look closely, our objective may be reduced to the issue of needing to locate the most laptops possible at any one time.
Here, the idea of a different array can be used. Here, we’ll indicate the start and end times using a hash map rather than an array.
Steps involved in the implementation of code:
- The start and end times of utilizing the laptop will be marked on a hash map in step one.
- Repeat Step 1 while iterating through the start and end arrays. When we try to store the number of laptops currently use, we will increase the hash value of start[i] by 1 and decrease the hash value of end[i] by 1.
- Third Step: We must employ a hash map data structure that is always sorted.
- We’ll keep a variable called “maxx” that stores the most laptops we might possibly need at any given time.
- Repeat the hash map iteratively, marking the beginning and ending points as +1 and -1, respectively. Maintain called cnt that represents the number of laptops that are currently in use.
- Add the hash map value to cnt and compare it to maxx after each iteration.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to calculate number of // laptops required int minLaptops( int N, vector< int >& start, vector< int >& end) { // Create an unordered_map to store the // start and end times of each // event and how many times they occur unordered_map< int , int > map; // Iterate over the start // times and increment their // count in the unordered_map for ( int i = 0; i < N; i++) { if (map.count(start[i])) map[start[i]]++; else map[start[i]] = 1; } // Iterate over the end times // and decrement their count // in the unordered_map for ( int i = 0; i < N; i++) { if (map.count(end[i])) map[end[i]]--; else map[end[i]] = -1; } // Create a 2D vector to store // the start and end times along // with their counts vector<vector< int > > res(2 * N, vector< int >(2, 0)); // Iterate over the unordered_map // and populate the 2D vector int ind = 0; for ( auto val : map) { res[ind][0] = val.first; res[ind][1] = val.second; ind++; } // Sort the 2D vector first by // start time, then by end time // (to break ties) sort(res.begin(), res.end(), []( const vector< int >& a, const vector< int >& b) { if (a[0] == b[0]) return a[1] < b[1]; else return a[0] < b[0]; }); // Initialize counters for the number // of laptops needed and the // maximum number of laptops needed int c = 0, ans = 0; // Iterate over the sorted 2D vector // and update the laptop counters for ( int i = 0; i < 2 * N; i++) { c += res[i][1]; ans = max(ans, c); } // Return the maximum number // of laptops needed return ans; } // Driver code int main() { // Sample inputs int N = 3; vector< int > start = { 1, 2, 3 }; vector< int > end = { 4, 4, 6 }; // Function call int minLaptopsRequired = minLaptops(N, start, end); // Print the output cout << minLaptopsRequired << endl; return 0; } // This code is contributed by prasad264 |
Java
// Java code for the above approach: import java.util.*; class GFG { // Function to calculate number of // laptops required public static int minLaptops( int N, int [] start, int [] end) { // Create a HashMap to store the // start and end times of each // event and how many times // they occur HashMap<Integer, Integer> map = new HashMap<>(); // Iterate over the start times // and increment their // count in the HashMap for ( int i = 0 ; i < N; i++) { if (map.containsKey(start[i])) map.put(start[i], map.get(start[i]) + 1 ); else map.put(start[i], 1 ); } // Iterate over the end times and // decrement their count // in the HashMap for ( int i = 0 ; i < N; i++) { if (map.containsKey(end[i])) map.put(end[i], map.get(end[i]) - 1 ); else map.put(end[i], - 1 ); } // Create a 2D array to store the // start and end times along // with their counts int [][] res = new int [ 2 * N][ 2 ]; // Iterate over the HashMap and // populate the 2D array int ind = 0 ; for (Map.Entry<Integer, Integer> val : map.entrySet()) { res[ind][ 0 ] = val.getKey(); res[ind][ 1 ] = val.getValue(); ind++; } // Sort the 2D array first by start // time, then by end time // (to break ties) Arrays.sort( res, Comparator.< int []>comparingInt(a -> a[ 0 ]) .thenComparingInt(a -> a[ 1 ])); // Initialize counters for the // number of laptops needed and the // maximum number of laptops needed int c = 0 , ans = 0 ; // Iterate over the sorted 2D array // and update the laptop counters for ( int i = 0 ; i < 2 * N; i++) { c += res[i][ 1 ]; ans = Math.max(ans, c); } // Return the maximum number // of laptops needed return ans; } // Driver code public static void main(String[] args) { // Sample inputs int N = 3 ; int [] start = { 1 , 2 , 3 }; int [] end = { 4 , 4 , 6 }; // Function call int minLaptops = minLaptops(N, start, end); // Print the output System.out.println(minLaptops); } } |
Python3
# Python3 code for the above approach from collections import defaultdict # Function to calculate number of laptops required def min_laptops(N, start, end): # Create a dictionary to store the start and end times of each event and how many times they occur d = defaultdict( int ) # Iterate over the start times and increment their count in the dictionary for i in range (N): d[start[i]] + = 1 # Iterate over the end times and decrement their count in the dictionary for i in range (N): d[end[i]] - = 1 # Create a list of tuples to store the start and end times along with their counts res = [] for key, value in d.items(): res.append((key, value)) # Sort the list of tuples first by start time, then by end time (to break ties) res.sort(key = lambda x: (x[ 0 ], x[ 1 ])) # Initialize counters for the number of laptops needed and the maximum number of laptops needed c, ans = 0 , 0 # Iterate over the sorted list of tuples and update the laptop counters for i in range ( len (res)): c + = res[i][ 1 ] ans = max (ans, c) # Return the maximum number of laptops needed return ans # Driver code if __name__ = = '__main__' : # Sample inputs N = 3 start = [ 1 , 2 , 3 ] end = [ 4 , 4 , 6 ] # Function call min_laptops_required = min_laptops(N, start, end) # Print the output print (min_laptops_required) |
C#
// C# code implementation using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to calculate number of laptops required public static int MinLaptops( int N, int [] start, int [] end) { // Create a Dictionary to store the start and end // times of each event and how many times they occur Dictionary< int , int > map = new Dictionary< int , int >(); // Iterate over the start times and increment their // count in the Dictionary for ( int i = 0; i < N; i++) { if (map.ContainsKey(start[i])) map[start[i]] = map[start[i]] + 1; else map[start[i]] = 1; } // Iterate over the end times and decrement their // count in the Dictionary for ( int i = 0; i < N; i++) { if (map.ContainsKey(end[i])) map[end[i]] = map[end[i]] - 1; else map[end[i]] = -1; } // Create a 2D array to store the start and end // times along with their counts int [][] res = new int [2 * N][]; for ( int i = 0; i < res.Length; i++) { res[i] = new int [2]; } // Iterate over the Dictionary and populate the 2D // array int ind = 0; foreach (KeyValuePair< int , int > val in map) { res[ind][0] = val.Key; res[ind][1] = val.Value; ind++; } // Sort the 2D array first by start time, then by // end time (to break ties) Array.Sort(res, (a, b) = > a[0].CompareTo(b[0]) != 0 ? a[0].CompareTo(b[0]) : a[1].CompareTo(b[1])); // Initialize counters for the number of laptops // needed and the maximum number of laptops needed int c = 0, ans = 0; // Iterate over the sorted 2D array and update the // laptop counters for ( int i = 0; i < 2 * N; i++) { c += res[i][1]; ans = Math.Max(ans, c); } // Return the maximum number of laptops needed return ans; } static public void Main() { // Code // Sample inputs int N = 3; int [] start = { 1, 2, 3 }; int [] end = { 4, 4, 6 }; // Function call int minLaptops = MinLaptops(N, start, end); // Print the output Console.WriteLine(minLaptops); } } // This code is contributed by karthik. |
Javascript
function minLaptops(N, start, end) { // Create an object to store the start and end times of each event // and how many times they occur let map = {}; // Iterate over the start times and increment their count in the object for (let i = 0; i < N; i++) { if (map[start[i]]) { map[start[i]]++; } else { map[start[i]] = 1; } } // Iterate over the end times and decrement their count in the object for (let i = 0; i < N; i++) { if (map[end[i]]) { map[end[i]]--; } else { map[end[i]] = -1; } } // Create a 2D array to store the start and end times along with their counts let res = Array(2 * N) .fill() .map(() => Array(2).fill(0)); // Iterate over the object and populate the 2D array let ind = 0; for (let [key, value] of Object.entries(map)) { res[ind][0] = parseInt(key); res[ind][1] = value; ind++; } // Sort the 2D array first by start time, then by end time (to break ties) res.sort((a, b) => { if (a[0] === b[0]) { return a[1] - b[1]; } else { return a[0] - b[0]; } }); // Initialize counters for the number of laptops needed and the maximum number of laptops needed let c = 0; let ans = 0; // Iterate over the sorted 2D array and update the laptop counters for (let i = 0; i < 2 * N; i++) { c += res[i][1]; ans = Math.max(ans, c); } // Return the maximum number of laptops needed return ans; } // Sample inputs let N = 3; let start = [1, 2, 3]; let end = [4, 4, 6]; // Function call let minLaptopsRequired = minLaptops(N, start, end); // Print the output console.log(minLaptopsRequired); |
3
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!