Given a 2d array arr[][] with each row representing a pair representing entry and exit time of a car in a parking lot, the task is to calculate the maximum number of cars that can be parked at the same time.
Examples:
Input: arr[][] = {{1012, 1136}, {1317, 1417}, {1015, 1020}}
Output: 2
Explanation:
1st car entered at 10:12 and exits at 11:36 and 3rd car entered at 10:15 and exits at 10:20.
Therefore, 1st and 3rd car are present at the same time.Input: arr[][] = {{1120, 1159}, {1508, 1529}, {1508, 1527}, {1503, 1600}, {1458, 1629}, {1224, 1313}}
Output: 4
Explanation: 2nd, 3rd, 4th and 5th cars are present at the same time.
Approach: The idea is to use Kadane’s algorithm to solve this problem. Follow the steps below to solve the problem:
- Initialize a vector of pairs to store the entry or exit time as the first element of a pair and true as the second element of a pair, if corresponding time stored is entry time. Otherwise, store as false.
- Sort the vector in non-decreasing order of time.
- Initialize two variables, say curMax, to look for all true contiguous segments of the array, and maxFinal, to keep track of longest true contiguous segment among all true segments.
- Iterate over the range [0, 2*N – 1]:
- If a car entered, increment curMax by 1.
- Otherwise:
- If curMax > maxFinal, update maxFinal = curMax.
- Whenever a car exits, subtract curMax by 1.
- Print maxFinal as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count maximum number// of cars parked at the sameint maxCars(int arr[][2], int N){ // Stores info about // entry and exit times pair<int, bool> a[2 * N]; // Convert given array to new array for (int i = 0; i < N; i++) { a[2 * i] = { arr[i][0], true }; a[2 * i + 1] = { arr[i][1], false }; } // Sort array in ascending // order of time sort(a, a + 2 * N); // Stores current maximum // at every iteration int curMax = 0; // Stores final maximum number // of cars parked at any time int maxFinal = 0; // Traverse the array for (int i = 0; i < 2 * N; ++i) { // When car entered if (a[i].second) { curMax++; } // When car exits else { if (curMax > maxFinal) { maxFinal = curMax; } curMax--; } } // Print the answer cout << maxFinal;}// Driver Codeint main(){ // Given array int arr[][2] = { { 1012, 1136 }, { 1317, 1412 }, { 1015, 1020 } }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call maxCars(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Pair classstatic class pair{ int first; boolean second; pair(int first, boolean second) { this.first = first; this.second = second; }}// Function to count maximum number// of cars parked at the samestatic void maxCars(int arr[][], int N){ // Stores info about // entry and exit times pair a[] = new pair[2 * N]; // Convert given array to new array for(int i = 0; i < N; i++) { a[2 * i] = new pair(arr[i][0], true); a[2 * i + 1] = new pair(arr[i][1], false); } // Sort array in ascending // order of time Arrays.sort(a, (p1, p2) -> p1.first - p2.first); // Stores current maximum // at every iteration int curMax = 0; // Stores final maximum number // of cars parked at any time int maxFinal = 0; // Traverse the array for(int i = 0; i < 2 * N; ++i) { // When car entered if (a[i].second) { curMax++; } // When car exits else { if (curMax > maxFinal) { maxFinal = curMax; } curMax--; } } // Print the answer System.out.println(maxFinal);}// Driver Codepublic static void main(String[] args){ // Given array int arr[][] = { { 1012, 1136 }, { 1317, 1412 }, { 1015, 1020 } }; // Size of the array int N = arr.length; // Function Call maxCars(arr, N);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to count maximum number# of cars parked at the samedef maxCars(arr, N): # Stores info about # entry and exit times a = [[0,True] for i in range(2 * N)] # Convert given array to new array for i in range(N): a[2 * i] = [arr[i][0], True] a[2 * i + 1] = [arr[i][1], False] # Sort array in ascending # order of time a = sorted(a) # Stores current maximum # at every iteration curMax = 0 # Stores final maximum number # of cars parked at any time maxFinal = 0 # Traverse the array for i in range(2*N): # When car entered if (a[i][1]): curMax += 1 # When car exits else: if (curMax > maxFinal): maxFinal = curMax curMax -= 1 # Print answer print (maxFinal)# Driver Codeif __name__ == '__main__': # Given array arr= [ [ 1012, 1136 ], [ 1317, 1412 ], [ 1015, 1020 ]] # Size of the array N = len(arr) # Function Call maxCars(arr, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{ // Function to count maximum number // of cars parked at the same static void maxCars(int[,] arr, int N) { // Stores info about // entry and exit times Tuple<int, bool>[] a = new Tuple<int, bool>[2 * N]; // Convert given array to new array for (int i = 0; i < N; i++) { a[2 * i] = new Tuple<int, bool>(arr[i,0], true); a[2 * i + 1] = new Tuple<int, bool>(arr[i,1], false); } // Stores current maximum // at every iteration int curMax = 1; // Stores final maximum number // of cars parked at any time int maxFinal = 0; // Traverse the array for (int i = 0; i < 2 * N; ++i) { // When car entered if (a[i].Item2) { curMax++; } // When car exits else { if (curMax > maxFinal) { maxFinal = curMax; } curMax--; } } // Print the answer Console.WriteLine(maxFinal); } static void Main () { // Given array int[,] arr = { { 1012, 1136 }, { 1317, 1412 }, { 1015, 1020 } }; // Size of the array int N = 2; // Function Call maxCars(arr, N); }}// This code is contributed by suresh07. |
Javascript
<script>// JavaScript program for the above approach// Pair classclass pair{ constructor(first,second) { this.first = first; this.second = second; }}// Function to count maximum number// of cars parked at the samefunction maxCars(arr,N){ // Stores info about // entry and exit times let a = new Array(2 * N); // Convert given array to new array for(let i = 0; i < N; i++) { a[2 * i] = new pair(arr[i][0], true); a[2 * i + 1] = new pair(arr[i][1], false); } // Sort array in ascending // order of time a.sort(function(p1, p2){return p1.first - p2.first}); // Stores current maximum // at every iteration let curMax = 0; // Stores final maximum number // of cars parked at any time let maxFinal = 0; // Traverse the array for(let i = 0; i < 2 * N; ++i) { // When car entered if (a[i].second) { curMax++; } // When car exits else { if (curMax > maxFinal) { maxFinal = curMax; } curMax--; } } // Print the answer document.write(maxFinal+"<br>");}// Driver Codelet arr=[[ 1012, 1136 ], [ 1317, 1412 ], [ 1015, 1020 ]];// Size of the arraylet N = arr.length;// Function CallmaxCars(arr, N);// This code is contributed by unknown2108</script> |
Output:
2
Time Complexity: O(NLogN)
Auxiliary Space: O(N)
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!
