title: Identify last passenger who enters the bus! - Meet Time Complexity
body: <p>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. </p>
  
  <p><strong><em>Test Case 1:</em></strong></p>
  
  <p><em>Input:</em></p>
  
  <ol>
  <li><p>Bus capacity a=2</p></li>
  <li><p>List of Patience limits b=[1,2,3,4]</p></li>
  <li><p>List of Time of bus arrival c=[1,3,4]</p></li>
  </ol>
  
  <p><em>Output:</em>
  [2,4,0]</p>
  
  <p>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.</p>
  
  <p>When the time of bus arrival(c[1]) is 3, passengers-1 &amp; 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.</p>
  
  <p>When the time of bus arrival(c[2]) is 4, passengers 1,2&amp; 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].</p>
  
  <p>I have coded the below in Java.</p>
  
  <pre><code> public static List&lt;Integer&gt; getLastPassenger(int a, List&lt;Integer&gt; b, List&lt;Integer&gt; c) {
  
      List&lt;Integer&gt; result = new ArrayList&lt;&gt;();
  
  
      for (int i = 0; i &lt; c.size(); i++) {  //1,3,4
  
          int count = 0;
          int j;
          for (j = 0; j &lt; b.size(); j++) { //1,2,3,4
  
              if (b.get(j) &gt;= c.get(i)) {
  
                  count++;
                  if (count == a) {
                      break;
                  }
  
              }
  
          }
          if (count &lt; a) {
              result.add(0);
          } else {
              result.add(j + 1);
          }
  
      }
  
      return result;
  }
  </code></pre>
  
  <p>But the code is not meeting time complexity, any help is really appreciated. </p>
  
  <p>Some More Test Cases:</p>
  
  <p><strong><em>Test Case 2:</em></strong></p>
  
  <p><em>Input:</em></p>
  
  <ol>
  <li><p>Bus capacity a=2</p></li>
  <li><p>List of Patience limits b=[2,2,2,3]</p></li>
  <li><p>List of Time of bus arrival c=[1,3,4]</p></li>
  </ol>
  
  <p><em>Output:</em>
  [2,0,0]</p>
  
  <p><strong><em>Test Case 3:</em></strong></p>
  
  <p><em>Input:</em></p>
  
  <ol>
  <li><p>Bus capacity a=2</p></li>
  <li><p>List of Patience limits b=[5,5,2,3,1]</p></li>
  <li><p>List of Time of bus arrival c=[1,3,4]</p></li>
  </ol>
  
  <p><em>Output:</em>
  [2,2,2]</p>
  
  <p><strong><em>Test Case 4:</em></strong></p>
  
  <p><em>Input:</em>
  1. Bus capacity a=3</p>
  
  <ol start="2">
  <li><p>List of Patience limits b=[1,1,1,4,4,3,2]</p></li>
  <li><p>List of Time of bus arrival c=[1,2,3,4]</p></li>
  </ol>
  
  <p><em>Output:</em>
  [3,6,6,0]</p>