CAC102 The Trains - CRACK-A-CODE 1.0 Editorial

editorial
, ,
1

PROBLEM LINK:

The Trains

Author: mayureshpatle
Tester: mayureshpatle
Editorialist: utkd52

DIFFICULTY:

EASY

PREREQUISITES:

Math, Maps

PROBLEM:

There are N trains running on M tracks. The i-th train currently has its ends at distances l_i and r_i from the starting of occupied track. Find the minimum value of M such that no two trains intersect or touch each other.

QUICK EXPLANATION:

We will simply find the point where there is intersection of maximum trains i.e. the point common to maximum number of trains. Thus the minimum number of track required will be the max value found.
To do this we will take the input of intervals and the sort them in n log n, after that traverse them to find out the point of maximum intersection witch will take n time.

EXPLANATION:

The logic to the solution is very obvious but the difficult part is how to implement it inside code.
We will take the input l_i , r_i sort them.
We will do two operations in every input

  1. We will increment the point l_i by 1 (Indicating a train starts here)
  2. We will decrement the point r_{i+1} by 1 (Indicating a train ends here)
    Note: r_{i+1} because, at the point r_i the train exists and at r_{i+1} its existence goes out.

The we will simply traverse this map while adding the values in our counter C. The maximum value of C at any stage will be the minimum tracks required for the trains to stand, as C is keeping the count of number of trains at that point.

SOLUTIONS:

Setter's Solution 
for _ in range(int(input())):
	c,a={},[]
	for _ in range(int(input())):
		l,r=map(int,input().split())
		if l in c: c[l]+=1
		else: c[l]=1;a.append(l)
		if r+1 in c: c[r+1]-=1
		else: c[r+1]=-1;a.append(r+1)
	x,ans,a=0,0,sorted(a)
	for i in a:
		x+=c[i]
		ans=max(ans,x)
	print(ans)
Editorialist's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll t,n,l,r,curr,maxx;
    cin>>t;
    while(t--)
    {
        cin>>n;
        map <ll,ll> pre;
        while(n--)
        {
            cin>>l>>r;
            ++pre[l];
            --pre[r+1];
        }
        curr=maxx=0;
        for(auto p:pre)
        {
            curr+=p.second;
            maxx=max(maxx,curr);
        }
        cout<<maxx<<endl;
    }
    return 0;
}
1 Like