Best way to optimize multiple search on Lists java
Problem Statement

This is my understanding of the problem statement.


We have a bus that has k seats.
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.
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&lt;Integer&gt; p = createList(people);
        int[] busTime = { 1, 4 };
        List&lt;Integer&gt; q = createList(busTime);
        List&lt;Integer&gt; f = busFilled(k, p, q);
        Integer[] output = 
                f.toArray(new Integer[0]);
        System.out.println("Result: " + 
                Arrays.asList(output));
    }

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

    public static List&lt;Integer&gt; busFilled(int k, 
            List&lt;Integer&gt; p, List&lt;Integer&gt; q) {
        List&lt;Integer&gt; output = new ArrayList&lt;&gt;();

        for (int i = 0; i &lt; 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&lt;Integer&gt; p, int busTime) {
        int count = 0;
        int index = -1;

        for (int i = 0; i &lt; p.size(); i++) {
            if (busTime &lt;= p.get(i)) {
                index = i;
                count++;
                if (count &gt;= 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.