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!
