Railway Station

Sample Examples

Example 1

Input : 

3
10 2
5 10
13 5

Output : 

2

Explanation :

The earliest arriving train at time t = 5 will arrive at platform# 1.

Since it will stay there till t = 15, train arriving at time t = 10 will arrive at platform# 2. Since it will depart at time t = 12, train arriving at time t = 13 will arrive at platform# 2.

Example 2

Input :

2
2 4
6 2

Output :

2

Explanation :

Platform #1 can accommodate train 1.

Platform #2 can accommodate train 2.

Note that the departure of train 1 is the same as the arrival of train 2, , i.e., 6, and thus we need a separate platform to accommodate train 2.

Approach

The idea is to go through each interval one by one and count how many overlap with it. Keep track of maximum interval numbers that can overlap with a given interval. Finally, return the highest possible value.

Take the following steps:

• Execute two nested loops, one from start to finish and the other from i+1 to finish.
• Calculate the number of intervals that intersect the current interval for each iteration of the outer loop.
• In each iteration of the outer loop, update the answer with the most overlap possible.
• The solution should be printed out.

Solution

In C++ programming language

#include<bits/stdc++.h>
using namespace std;

void solution(int arr1[], int arr2[], int size)
{
    sort(arr1,arr1+size);
    sort(arr2,arr2+size);
    int x=1,y=1;
    int i=1,j=0;
    while(i<size && j<size)
    {
        if(arr1[i]<=arr2[j])
        {
            x++;
            i++;
        }
        else if(arr1[i]>arr2[j])
        {
            x--;
            j++;
        }
        if(x>y)
            y=x;
    }
    cout<<y;
}

int main()
{
    int size;
    cin>>size;
    int arr1[size],arr2[size];
    for(int i=0;i<size;i++)
    {
        cin>>arr1[i]>>arr2[i];
        arr2[i]=arr1[i]+arr2[i];
    }

    solution(arr1,arr2, size);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

3
10 2
5 10
13 5

You can also try this code with Online C++ Compiler

Run Code

Output :

2

You can also try this code with Online C++ Compiler

Run Code

In Java programming language

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int[] ar = new int[n];
        int[] dep = new int[n];
        for (int i = 0; i < n; i++) {
            ar[i] = scn.nextInt();
            int stoppage = scn.nextInt();
            dep[i] = ar[i] + stoppage;
        }
        solution(ar, dep, n);
  scn.close();
    }

    public static void solution(int [] ar, int []depar, int size) {
        Arrays.sort(ar);
        Arrays.sort(depar);
        int i = 1, j = 0, currPlatform = 1, ans = 1;
        while (i < size && j < size) {
            if (ar[i] <= depar[j]) {
                i++;
                currPlatform++;
            }
            else {
                currPlatform--;
                j++;
            }
            ans = Math.max(currPlatform, ans);
        }
        System.out.println(ans);
    }
}

You can also try this code with Online Java Compiler

Run Code

Input:

3
10 2
5 10
13 5

You can also try this code with Online Java Compiler

Run Code

Output :

2

You can also try this code with Online Java Compiler

Run Code

In Python programming language

size = int(input())
ar = []
depar = []
for i in range(size):
  x, y = map(int, input().split())
  y += x
  ar.append(x)
  depar.append(y)
ar.sort()
depar.sort()
i = 1
j = 0
currPlf = 1
ans = 1
while i<size and j<size:
  if ar[i] <= depar[j]:
    i+=1
    currPlf+=1
    ans = max ( ans, currPlf )
    continue
  j+=1
  currPlf-=1
print(ans)

You can also try this code with Online Python Compiler

Run Code

Input:

3
10 2
5 10
13 5

You can also try this code with Online Python Compiler

Run Code

Output :

2

You can also try this code with Online Python Compiler

Run Code

Time Complexity: O(N log N)+O(N)

Space Complexity: O(N)

where N represents the size of the array.

Frequently Asked Questions

1. What is TCS CodeVita?
   TCS CodeVita is an online 24-hours coding test held at a global level.
    
2. What is the output of the TCS CodeVita previous year's railway station problem?
   In this codevita previous year's problem, we need to determine the minimum number of platforms required for the given input.

Conclusion

In this article, we have extensively discussed the railway station problem of TCS codevita and their implementation in different programming languages.

The railway station problem is the previous year's TCS codevita question in which we need to find the minimum number of platforms required for the given input. 

Check out this article to find out everything about TCS NQT.

We hope this blog has helped you enhance your knowledge regarding the railway station TCS codevita problem. If you would like to learn more, check out our articles on the minimum number of platforms needed, minimum number of platforms, naksha, and occupy all trains. Do upvote our blog to help other ninjas grow. Happy Coding!