Identify last passenger who enters the bus! - Meet Time Complexity

user_13467666 0
Viewed 1804

This is a question asked in my interview. There are a number of passengers waiting in a queue. Initially, the bus is assumed to be empty and has a fixed capacity "a". I am trying to find the last person who is entering a bus based on his patience level in accordance with the bus time. The person will be waiting for the bus until his patience level expires. In the end, if all the passengers are boarded, 0 is returned because there will be no person left.

Test Case 1:

Input:

  1. Bus capacity a=2

  2. List of Patience limits b=[1,2,3,4]

  3. List of Time of bus arrival c=[1,3,4]

Output: [2,4,0]

In this scenario, when the time of bus arrival(c[0]) is 1, all the passengers will be available( coz the patience level of all passengers is above bus time i.e 1). But as the bus capacity is limited to 2, only 2 passengers are allowed to enter. So only 2 passengers up to position 2 of the queue will be able to enter. So, the answer to the first query of bus arrival is 2.

When the time of bus arrival(c[1]) is 3, passengers-1 & 2 will not be available as their patience level is exceeded, hence passengers at positions 3 and 4 will be entering according to the capacity. So, the answer to the second query of bus arrival is 4.

When the time of bus arrival(c[2]) is 4, passengers 1,2& 3 would have left queue already, hence passenger 4 will be ready to enter, but as the capacity is not met, 0 is returned. So, final solution is [2,4,0].

I have coded the below in Java.

 public static List<Integer> getLastPassenger(int a, List<Integer> b, List<Integer> c) {

    List<Integer> result = new ArrayList<>();


    for (int i = 0; i < c.size(); i++) {  //1,3,4

        int count = 0;
        int j;
        for (j = 0; j < b.size(); j++) { //1,2,3,4

            if (b.get(j) >= c.get(i)) {

                count++;
                if (count == a) {
                    break;
                }

            }

        }
        if (count < a) {
            result.add(0);
        } else {
            result.add(j + 1);
        }

    }

    return result;
}

But the code is not meeting time complexity, any help is really appreciated.

Some More Test Cases:

Test Case 2:

Input:

  1. Bus capacity a=2

  2. List of Patience limits b=[2,2,2,3]

  3. List of Time of bus arrival c=[1,3,4]

Output: [2,0,0]

Test Case 3:

Input:

  1. Bus capacity a=2

  2. List of Patience limits b=[5,5,2,3,1]

  3. List of Time of bus arrival c=[1,3,4]

Output: [2,2,2]

Test Case 4:

Input: 1. Bus capacity a=3

  1. List of Patience limits b=[1,1,1,4,4,3,2]

  2. List of Time of bus arrival c=[1,2,3,4]

Output: [3,6,6,0]

data-structures time-complexity algorithm java performance
2 Answers
user_108025970

For future queries,I was able to optimize the question using C++. I could not resolve on time, but I think this approach will pass the time restrictions


    class BusStand{
        multimap<int,size_t> stand;
    public:
        void add(const int patience, const size_t order){
            stand.insert(std::make_pair(patience, order+1));
        }
        size_t getOrder(int patience, int k){
            vector<int> orders;
            auto it = stand.find(patience);
            if(it == stand.end()){
                it = stand.upper_bound(patience);
            }
            for(; it != stand.end(); ++it){
                orders.push_back(it->second);
            }
            if(k > orders.size())
                return 0;
    
            sort(orders.begin(), orders.end());
            return orders[k-1];
        }
    };
    
    vector<int> getLastPassenger(int k, vector<int> p, vector<int> q) {
        vector<int> results;
        BusStand stand;
        size_t i = 0;
        for(const int & c: p){
            stand.add(c, i++);
        }
    
        for(const int & c : q){
            const auto r =stand.getOrder(c,k);
            results.push_back(r);
        }
        return results;
    }
user_19672210
Related