Блог пользователя YashShah

Автор YashShah, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

You should always provide links to any source webpage, if possible.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

The amount of people entering the bust is non-decreasing as you go right in the array. Also, since queries are independent, you can answer them in any order you would like.

Let ds[] be an array used for some data structure that can do point updates and answer range sum queries in $$$\mathcal{O}(logN)$$$ time. Sort both arrays and, for each query $$$q_j$$$, move right on the passenger's array until you find a patience level $$$p_i \geq q_j$$$. For every other patience level $$$p_{i - 1}, p_{i - 2}, ... < p_i$$$ we increase the array ds[p[i - 1]], ds[p[i - 2]], ... by $$$1$$$.

edited: Forgot to mention. To answer the queries you can binary search the last position $$$x$$$ that is going to enter the bus. Query the sum in range $$$[0 .. x]$$$ and call that $$$q_{ans}$$$. The amount of valid people in this range is $$$x + 1 - q_{ans}$$$. If it's greater than or equal to the capacity, lower the search bounds. Otherwise, increase the search bounds. I guess it's not $$$\mathcal{O}(NlogN)$$$, but $$$\mathcal{O}(Nlog^2N)$$$?

This way we answer all queries in $$$\mathcal{O}(NlogN)$$$ time. Traversing the entire array just once and doing at most $$$\mathcal{O}(logN)$$$ operations on each position.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We need to iterate the patience list without sorting. If sorting is done, then the index will be missed.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You are preserving their indexes by increasing the corresponding position in the data structure by one.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I’m trying to implement this solution, but I couldn’t understand this second part. Must I binary search in ds[ ] or p[ ]? Could you explain better how to get this last position x? After that, I believe that I should get the sum in ds[ ] in the range [0..x] = qans, and apply this formula: x + 1 — qans;

    Could you clarify this second part? Thanks.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Binary search on ds[].

      For instance, input is $$$[3, 1, 1, 4]$$$. You will get p[] = {1, 1, 3, 4}. When processing the query $$$t = 2$$$, your data structure will look like this: ds[] = {0, 1, 1, 0}.

      The binary search part: Let's say I'm querying the range $$$[0, 3]$$$ on the same example. The length is $$$4$$$, and the query result is 2. Therefore, two people inside this range are still waiting for the bus. What if the capacity is $$$1$$$? This means I need to lower the right bound. When querying range $$$[0, 2]$$$, length is $$$3$$$ and query result is $$$2$$$, which means that only one person is entering the bus.

      So yes, the binary search is on the data structure. For each tested value $$$x$$$, you will query the data structure on the range $$$[0, x]$$$ and do the math to see if it's valid.