I got this question from the interviewbit site test.

There are n horses and you are the kth person in the line to ride on the horse. All the persons in the queue will go with the lowest numbered horse available i.e if horse no.1 and horse no.2 are present , the person will choose horse no.1 .All the horses have their own riding time and after their riding time ends they are free for next round. If there are no horses available the person will wait for the horse to come and will go on with it. We have to find that on which horse number we will be riding.

Input:- T - no. of test cases, n - no. of horses, k - your number in queue,ride time(M) - n numbers which will denote the riding time of the horses

constraints:- 1 <= T <= 100, 1 <= N <= 1000, 1 <= K <= 10^9, 1 <= M(i) <= 100000

output :- you have to tell the horse number which you will get.

Ex. 1

3 8

4 2 1

output:-
1

Here there are 3 horses with running time 4, 2, 1 and i am 8th in the queue.
so first three persons will go with horse#1 , horse#2 and horse#3. After this
there will be no horse so the fourth person will have to wait. horse#3 will
come first so he will go with it. fifth will go with horse#2 and sixth with
horse#3, seventh will go with horse#3 and eight will go with horse #1. so the
output is 1.

Below is my code :-

Its time complexity is O(N*K). Is there a better way to solve it.

#include<iostream>
using namespace std;

int main()

 int t;
 cin>>t;
 while(t--)
 int n,k;
 cin>>n>>k;
 int hrs[n], ans;
 for(int i = 0;i < n;i++)
 cin>>hrs[i];

 if(n >= k)
 cout<<k<<endl;
 else
 int tt = 0,p = n;
 int B[n];
 for(int j = 0;j < n;j++)
 B[j] = hrs[j];

 while(p != k)
 tt++;
 for(int m = 0;m < n;m++)
 if(tt == hrs[m])
 p++;
 hrs[m] += B[m];
 if(p == k)
 ans = m;
 break;
 
 
 

 
 cout<<ans+1<<endl;
 

 

 return 0;

Use portable constructs

Variable-length arrays are not standard C++. Using such non-standard extensions hampers your code because you can't easily use different compilers (this can possibly even exclude entire target platforms).

Avoid importing all of std into the global namespace

Namespaces provide us with an important service, separating the large and growing set of identifiers in std from those of our own code. It's actively harmful to reverse that benefit with using namespace std.

Always test for errors when reading

Formatted input such as std::cin >> n >> k should always test the state of the stream before using the read values.

Use clearer names

We don't have to use names like t just because that's what the question uses to describe the number of test cases. Similarly, hrs took me much longer to comprehend than would horse - and that's not going to push your line lengths.

Know your standard library

What we have is a priority queue of horses, ordered by the time they next return, with the horse's number as tie-breaker. We have std::priority_queue with insertion/removal times that scale as O(log n), so iterating over the k previous riders to find which horse we get will scale as O(k log n).

The algorithm is pretty simple - for each member of the queue in front of us, take the next horse from the stable (a std::priority_queue), add its running time to its next-available time, and insert it back into the stable. The horse at the front of the stable after k-1 iterations will be ours.