Railway Station Codevita 9 Solution

by

Railway Station Codevita 9 Solution 2020

Given timetable of trains and their stoppage time at a Railway Station, discover least number of stages required.

Note: In the event that Train A’s flight time is x and Train B’s appearance time is x, at that point we can’t oblige Train B on a similar stage as Train A.

Constraints

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

Input

  • First line contains N signifying number of trains. 
  • Next N line contain 2 whole numbers, an and b, indicating the appearance time and stoppage season of train. 

Output

Single whole number indicating the base quantities of stages expected to oblige each train. 

Time Limit 

1 

Models 

Model 1 

Input

3 

10 2 

5 10 

13 5 

Output

2 

Explanation

The soonest showing up train at time t = 5 will show up at platform# 1. Since it will remain there till t = 15, train showing up at time t = 10 will show up at platform# 2. Since it will withdraw at time t = 12, train showing up at time t = 13 will show up at platform# 2.

SOLUTION

Program: Railway Station Codevita 9 Solution in C++

#include <bits/stdc++.h> 
using namespace std;
const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;
 
typedef short unsigned int sui; // 0 to 65,535
typedef int i; // -2147483648 to 2147483647
typedef unsigned int ui; // 0 to 4294967295
typedef unsigned long int uli; // 0 to 4,294,967,295
typedef long long ll; //range -(2^63) to (2^63)-1
typedef unsigned long long ull;
 
typedef vector<int> vi; 
typedef pair<int, int> ii; 
typedef vector<ii> vii;
typedef vector<vi> vvi;
 
struct node {
    ui a;
    ui d;
};
 
#define LSOne(S) (S & (-S))
#define isBitSet(S, i) ((S >> i) & 1)
 
 

int cmp( node x, node y ){
    return x.a < y.a;
}
 
bool trackEmpty(vi track, int a){
    bool flag = false;
    if(track.empty()){
        return true;
    }
    else{
        for( auto i = track.begin(); i < track.end(); i++){
            if ( *i < a ){
                track.erase(i);
                flag = true;
                break;
            }
        }
        return flag;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 

    ull n; 
    cin >> n;
 
    node train[n];
    for (ull t = 0; t<n ; t++){
        cin >> train[t].a >> train[t].d;
        train[t].d = train[t].a + train[t].d;
    }
 
    sort(train, train+n, cmp);
    vi track;
    ui maxSize = 1;
    for(auto i: train){
        if(trackEmpty(track, i.a)){
            track.push_back(i.d);
        }
        else{
            track.push_back(i.d);
            maxSize = max(maxSize, static_cast<unsigned int> (track.size()));
        }
    }
    cout << maxSize;
    return 0;
}

Codevita Season 9 All Questions Solution

Leave a Comment

19 − 5 =