In this HackerEarth Taxi Please! problem solution Today, you have been given the task of handling the entire Taxi Network of Berland City. Berland city has a huge number of taxi travellers, and you need to help them in transportation in the most efficient manner.

To be precise, this city consists of N users who want to travel via a Taxi today. You have a total of M taxis and need to cater to the users using these taxis. Each user has two parameters associated with them,  and , denoting the time at which a user requests a taxi and the travel time required to reach the destination of this particular user. Each taxi can be used by a maximum of 1 user at each point in time.

If, at any point in time a user requests a taxi and all M taxis are busy, then this user's request is rejected. If multiple taxis are available at the time of the request of a user, the taxi with the lowest index that is available is alloted to them. Now, you need to find for each user, the index of the taxi alloted to them. If a particular user's request is rejected, print "-1" (without quotes) for them.


HackerEarth Taxi Please! problem solution


HackerEarth Taxi Please! problem solution.

import java.io.*;
import java.util.*;
class taxi
{
static Scanner sc;
static PrintWriter out;

static void init() throws Exception
{
sc=new Scanner(System.in);
out=new PrintWriter(System.out);
}

public static void main(String args[]) throws Exception
{
init();
int n=sc.nextInt(),m=sc.nextInt();
Node[] a=new Node[n];
for(int i=0;i<n;i++)
{
a[i]=new Node(i,sc.nextLong(),sc.nextLong());
}
Arrays.sort(a);
long[] last=new long[m],res=new long[n];
for(int i=0;i<n;i++)
{
boolean used=false;
for(int j=0;j<m;j++)
{
if(last[j]<=a[i].a)
{
res[a[i].idx]=j+1;
last[j]=a[i].a+a[i].b;
used=true;
break;
}
}
if(!used)
{
res[a[i].idx]=-1;
}
}
for(long x:res)
{
out.print(x+" ");
}
out.close();
}
}
class Node implements Comparable<Node>
{
int idx;
long a,b;
public Node(int idx,long a,long b)
{
this.idx=idx;
this.a=a;
this.b=b;
}
public int compareTo(Node x)
{
return Long.compare(this.a,x.a);
}
}