YashShah's blog

By YashShah, history, 4 years ago, In English

This is the algorithmic problem found on StackOverflow in which I have updated some Test Cases. How to optimize the solution to the problem mentioned below:

There are a number of passengers waiting in a queue. Initially, the bus is assumed to be empty and has a fixed capacity "a". We need 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:

Bus capacity a=2

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

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].

Test Case 2:

Input:

Bus capacity a=2

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

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

Output: [2,0,0]

Test Case 3:

Input:

Bus capacity a=2

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

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

Output: [2,2,2]

Test Case 4:

Input:

Bus capacity a=3

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

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

Output: [3,6,6,0]

Java Code mentioned below exceeded the time limit, any help is really appreciated.

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++) {  //List of Time Of Bus arrival

        int count = 0;
        int j;
        for (j = 0; j < b.size(); j++) { //List of Patience limits of passengers

            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;
}

UPDATE 1: Link to a problem on StackOverflow -> https://stackoverflow.com/questions/62287122/identify-last-passenger-who-enters-the-bus-meet-time-complexity

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it