RAILS -EDITORIAL

PROBLEM LINK:

Practice
Contest

Author: rocknot
Tester: yogesh_5326
Editorialist:rocknot

DIFFICULTY:

EASY

PREREQUISITES:

Implementation

PROBLEM:

Aditya just completed his final exams and now it time for vacation. After a while he got bored so he decided to plan for a short trip, so he asked some of his friends and just for enjoyment they decided to travel as many trains as they can. So the checked the schedules of the trains and found out common timings of all the trains on different stations and listed them. Now they need to determine the schedule such that they can change maximum no of trains. You are given two list of size N denoting the start position S[N] and end position E[N] of the trains you need to determine the maximum no of trains they can change. It is to be noted that you can only travel if ending position of train on which you are is = the starting position of next train and your starting position will be 0.

EXPLANATION:

Create A structure to store the starting positions and ending positions and sort them according to order of increasing value of end times. and then find the count until the start time is greater than end time. and print the count.

SOLUTIONS:

Solution
#include <bits/stdc++.h>
using namespace std;
struct Activitiy{
    int start, finish;
};
bool activityCompare(Activitiy s1, Activitiy s2)
{
    return (s1.finish < s2.finish);
}
void printMaxActivities(Activitiy arr[], int n){
sort(arr, arr+n, activityCompare);
int i = 0,temp =1;


for (int j = 1; j < n; j++)
{
  if (arr[j].start >= arr[i].finish)
  {
      temp++;
      i = j;
  }
}
cout<<temp<<endl;

}

int main(){
int T;
cin>>T;
while(T--){
    int N,temp;
    cin>>N;
    Activitiy arr[N];
    for(int i=0;i<N;i++){
        cin>>temp;
        arr[i].start=temp;
    }
    for(int i=0;i<N;i++){
        cin>>temp;
        arr[i].finish=temp;
    }
    printMaxActivities(arr, N);
}
return 0;

}