Railway Station Problem

Railway station problem is one of the problem that was asked in previous year TCS Codevita Exam. In this problem we have given schedule of train and their stoppage time at a railway station and we have to find the minimum number of platform needed to accommodate every train.

Problem Description

Given schedule of trains and their stoppage time at a Railway Station, find minimum number of platforms needed.

Note –

If Train A’s departure time is x and Train B’s arrival time is x, then we can’t accommodate Train B on the same platform as Train A.

Constraints

1 <= N <= 10^5
0 <= a <= 86400
0 < b <= 86400
Number of platforms > 0

Input

First line contains N denoting number of trains.
Next N line contain 2 integers, a and b, denoting the arrival time and stoppage time of train.

Output

Single integer denoting the minimum numbers of platforms needed to accommodate every train.

Example 1

Input

10 2

5 10

13 5

Output

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 4

6 2

Output

Explanation

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

Java

import java.util.*;

class Main 
{
    public static void main (String[]args) 
    {
        Scanner sc = new Scanner (System.in);
        int n = sc.nextInt ();
        
        int a[] = new int[n];
        int b[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = sc.nextInt ();
            b[i] = sc.nextInt ();
            b[i] = a[i] + b[i];
        } 
        Arrays.sort (a);
        Arrays.sort (b);
        int i = 1, j = 0, p = 1, q = 1;
        while (i < n && j < n)
        {
	        if (a[i] <= b[j])
        	{
                p++;
                i++;
            }
        	else if (a[i] > b[j])
    	    {
                p--;
                j++;
            }
            if (p > q)
                q = p;
        }
        System.out.println (q);
    }
}

Positive or Negative number: C | C++ | Java
Even or Odd number: C | C++ | Java
Sum of First N Natural numbers: C | C++ | Java
Sum of N natural numbers: C | C++ | Java
Sum of numbers in a given range: C | C++ | Java
Greatest of two numbers: C | C++ | Java
Greatest of the Three numbers: C | C++ | Java
Leap year or not: C | C++ | Java
Prime number: C | C++ | Java
Prime number within a given range: C | C++ | Java
Factorial of a number: C | C++ | Java
Sum of digits of a number: C | C++ | Java
Reverse of a number : C | C++ | Java
Palindrome number: C | C++ | Java
Armstrong number : C | C++ | Java
Armstrong number in a given range : C | C++ | Java
Fibonacci Series upto nth term : C | C++ | Java
Factorial of a number : C | C++ | Java
Power of a number : C | C++ | Java
Factor of a number : C | C++ | Java
Strong number : C | C++ | Java
Perfect number : C | C++ | Java
Automorphic number : C | C++ | Java
Harshad number : C | C++ | Java
Abundant number : C| C++ | Java
Friendly pair : C | C++ | Java

One comment on “Railway Station Problem (TCS Codevita)”

aneesh
n=int(input())
c=[]
for i in range(n):
k=list(map(int,input().split()))
c.append([k[0],sum(k)])
c.sort(key=lambda x:x[0])
l=[[c[0]]]
for i in range(1,len(c)):
y=0
for j in range(0,len(l)):
if l[j][len(l[j])-1][1]<c[i][0]:
l[j].append(c[i])
y=1
if y==0:
l.append([c[i]])
print(len(l))

0

Log in to Reply