Count maximum number of cars parked at the same time

0 0 6 minutes read

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:
1^st car entered at 10:12 and exits at 11:36 and 3^rd car entered at 10:15 and exits at 10:20.
Therefore, 1^st and 3^rd car are present at the same time.

Input: arr[][] = {{1120, 1159}, {1508, 1529}, {1508, 1527}, {1503, 1600}, {1458, 1629}, {1224, 1313}}
Output: 4
Explanation: 2^nd, 3^rd, 4^th and 5^th 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 same
int 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 Code
int 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 approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Pair class
static 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 same
static 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 Code
public 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 same
def 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 Code
if __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 approach
using 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 class
class pair
{
    constructor(first,second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to count maximum number
// of cars parked at the same
function 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 Code
let arr=[[ 1012, 1136 ],
                    [ 1317, 1412 ],
                    [ 1015, 1020 ]];
// Size of the array
let N = arr.length;
 
// Function Call
maxCars(arr, N);
 
 
// This code is contributed by unknown2108
 
</script>

Output:

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 zambiatek!