Best way to optimize multiple search on Lists java

Anyone could help me to optimize this block of code, I already did a bit improvement but since I’m really bad with this kind of algorithms this all I’ve done so far. Much appreciate if you can explain the improvement.

This basically fill a bus (k is the number of seats on the bus) if all seats are filled save the last index of the person who gets into the bus.

p is a list of persons waiting the bus (each person has patience limit) q is a list of time the bus will take to arrive.

Example;

k=2
p={1,4,2,5}
q={1,4}

On the first time bus will arrive in time 1 so person 1 and 2 will fill the bus and index of person will be saved in a list (r={2}).

On the second time bus will arribe in time 4, person 1 and 3 leave person 2 and 4 fill the bus (r={2,4}).

If the bus can’t be filled then the number saved in the list is 0.

public static List<Integer> busFilled(int k, List<Integer> p, List<Integer> q) {

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

    // Sort the times of bus arrival
    Collections.sort(q);

    // Loop each bus arrival
    for(int time : q) {
        // If person patience < time set the patience to 0
        for (int i=0; i<p.size()-1; i++) {
            if (p.get(i) < time) {
                p.set(i, 0);
            }
        }

        int aux = 0;
        // Loop each person patience
        for (int i=0; i<=p.size()-1; i++) {
            // If person patience > 0 count
            if ( p.get(i) > 0) {
                aux++;
            }

            // If aux = bus seats add the last number(index) of person who filled the bus
            if (aux == k) {
                busSeats.add(i+1);
                break;
            // If i == total persons in queue set 0
            } else if (i==p.size()-1){
                busSeats.add(0);
            }
        }
    }
    return busSeats;
}

Problem Statement

This is my understanding of the problem statement.

1. We have a bus that has k seats.

2. There is a list of people p waiting at a bus stop. The value in each position of the list is the amount of time the person is willing to wait for a bus. The list is replenished for each scheduled time the bus arrives. The wait times do not change with new people.

3. There is a list of scheduled times q that the bus will arrive.

The method busFilled returns a List of the index of the last person to get on the bus each time the bus arrives at the bus stop. There should be the same number of elements in the output List as there are in the list of scheduled times q.

If no one can fit on the bus, the List should return zero in that position.

Analysis

I approached the problem the same way I approach any problem. I break the problem down into smaller and smaller steps until I can write code for each of the steps.

Here’s the code I wrote. The explanation follows the code.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BusSimulation {

    public static void main(String[] args) {
        int k = 2;
        int[] people = { 1, 4, 2, 5 };
        List<Integer> p = createList(people);
        int[] busTime = { 1, 4 };
        List<Integer> q = createList(busTime);
        List<Integer> f = busFilled(k, p, q);
        Integer[] output = 
                f.toArray(new Integer[0]);
        System.out.println("Result: " + 
                Arrays.asList(output));
    }

    public static List<Integer> createList(int[] array) {
        List<Integer> output = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            output.add(array[i]);
        }
        return output;
    }

    public static List<Integer> busFilled(int k, 
            List<Integer> p, List<Integer> q) {
        List<Integer> output = new ArrayList<>();

        for (int i = 0; i < q.size(); i++) {
            int busTime = q.get(i);
            int index = getPassengerIndex(k, p, busTime);
            output.add(index);
        }

        return output;
    }

    private static int getPassengerIndex(int k, 
            List<Integer> p, int busTime) {
        int count = 0;
        int index = -1;

        for (int i = 0; i < p.size(); i++) {
            if (busTime <= p.get(i)) {
                index = i;
                count++;
                if (count >= k) {
                    return index + 1;
                }
            }
        }

        return index + 1;
    }

}

The main method and the createList method set up the problem.

I created a separate method, getPassengerIndex, to get the passenger index for one bus trip. That way, I avoided a nested for loop and worrying about how to break out of the nested for loop.

The getPassengerIndex method loops through the passenger list. First, I test to see if the waiting time has been exceeded. If not, then I save the index and increment the count of the number of passengers boarding the bus. Finally, I test for the bus being filled. If so, I return the passenger number. If the bus isn’t filled, I return the last passenger number whose waiting time has not been exceeded.

I could test getPassengerIndex separate from the rest of the code. Once I got that method working, writing the busFilled method was straight forward.

Decomposition, or divide and conquer, is the most straightforward way to solve problems.