title: Reducing time complexity for the given task
body: <p>I have an item that has a name and a price for it.</p>
  <p>Now input for my program contains some list of commands which indicate I can add new item or select an item in the following format:</p>
  <blockquote>
  <p>Add, item-name, item-price --&gt; Adds item-name with price item-price to my list.
  Select, ,  --&gt; select the item name that has lowest price at index k, and prints to output. If multiple items has same price then select the name in ascending order.</p>
  </blockquote>
  <p><strong>Example 1:</strong></p>
  <p><strong>Input :</strong></p>
  <pre><code>Add, Apple, 4
  Add, Ball, 3
  Select, , 
  Add, Toy, 5
  Add, Pen, 1
  Select, , 
  </code></pre>
  <p><strong>Output:</strong></p>
  <pre><code>Ball, Ball
  </code></pre>
  <p><strong>Explanation:</strong></p>
  <blockquote>
  <p>First we add Apple and Ball. So the items sorted by price [Ball(3), Apple(4)]. Initialize k to 0.
  Then Select has appeared. So get item at index k=0 which is Ball. Now increment k to 1 as a selection has occurred.
  Then we add Toy and Pen. So the items sorted by price [Pen(1), Ball(3), Apple(4), Toy(5)] . Now k is 1.
  Then Select has appeared. So get item at index k=1 which is Ball again. Now increment k to 2 as a selection has occurred.</p>
  </blockquote>
  <pre><code>So output is Ball, Ball.
  </code></pre>
  <p><strong>Example 2:</strong></p>
  <p><strong>Input :</strong></p>
  <pre><code>Add, Apple, 4
  Add, Ball, 3
  Select, , 
  Select, , 
  Add, Toy, 5
  Select, , 
  </code></pre>
  <p><strong>Output:</strong></p>
  <pre><code>Ball, Apple, Toy
  </code></pre>
  <p><strong>Explanation:</strong></p>
  <blockquote>
  <p>First we add Apple and Ball. So the items sorted by price [Ball(3), Apple(4)]. Initialize k to 0.
  Then Select has appeared. So get item at index k=0 which is Ball. Now increment k to 1 as a selection has occurred.
  Then Select has appeared. So get item at index k=1 which is Apple. Now increment k to 2 as a selection has occurred.
  Then we add Toy. So the items sorted by price [Ball(3), Apple(4), Toy(5)] . Now k is 2.
  Then Select has appeared. So get item at index k=2 which is Toy. Now increment k to 3 as a selection has occurred.</p>
  </blockquote>
  <pre><code>So output is Ball, Apple, Toy.
  </code></pre>
  <p>This is the code I tried:</p>
  <pre><code>public static void main(String[] args) {
          System.out.println(process(Arrays.asList(Arrays.asList(&quot;Add&quot;, &quot;Apple&quot;, &quot;4&quot;), Arrays.asList(&quot;Add&quot;, &quot;Ball&quot;, &quot;3&quot;),
                  Arrays.asList(&quot;Select&quot;, &quot;&quot;, &quot;&quot;), Arrays.asList(&quot;Add&quot;, &quot;Toy&quot;, &quot;5&quot;), Arrays.asList(&quot;Add&quot;, &quot;Pen&quot;, &quot;1&quot;),
                  Arrays.asList(&quot;Select&quot;, &quot;&quot;, &quot;&quot;))));
  
          System.out.println(process(Arrays.asList(Arrays.asList(&quot;Add&quot;, &quot;Apple&quot;, &quot;4&quot;), Arrays.asList(&quot;Add&quot;, &quot;Ball&quot;, &quot;3&quot;),
                  Arrays.asList(&quot;Select&quot;, &quot;&quot;, &quot;&quot;), Arrays.asList(&quot;Select&quot;, &quot;&quot;, &quot;&quot;), Arrays.asList(&quot;Add&quot;, &quot;Toy&quot;, &quot;5&quot;),
                  Arrays.asList(&quot;Select&quot;, &quot;&quot;, &quot;&quot;))));
      }
  
      public static List&lt;String&gt; process(List&lt;List&lt;String&gt;&gt; input) {
          List&lt;String&gt; list = new ArrayList&lt;&gt;();
          PriorityQueue&lt;Item&gt; pq = new PriorityQueue&lt;&gt;();
          int k = 0;
          for (List&lt;String&gt; e : input) {
              if (&quot;Add&quot;.equals(e.get(0))) {
                  Item a = new Item(e.get(1), e.get(2));
                  pq.add(a);
              } else {
                  List&lt;Item&gt; sorted = new ArrayList&lt;&gt;();
                  for (int i = 0; i &lt;= k; i++) {
                      sorted.add(pq.poll());
                  }
                  Item itemAtK = sorted.get(sorted.size() - 1);
                  list.add(itemAtK.name);
                  pq.addAll(sorted);
                  k++;
              }
          }
          return list;
      }
  
  }
  
  class Item implements Comparable&lt;Item&gt; {
      int price;
      String name;
  
      public Item(String name, String p) {
          this.name = name;
          this.price = Integer.parseInt(p);
      }
  
      public int compareTo(Item item) {
          int c = price - item.price;
          if (c == 0)
              c = name.compareTo(item.name);
          return c;
      }
  </code></pre>
  <p>Here time complexity is I guess <code>n^2*log(n)</code></p>
  <p>How to reduce the time complexity for this code.</p>
  <p><strong>Modified code based on stef comments:</strong></p>
  <pre><code>public static List&lt;String&gt; process(List&lt;List&lt;String&gt;&gt; input) {
          List&lt;String&gt; list = new ArrayList&lt;&gt;();
          PriorityQueue&lt;Item&gt; pq = new PriorityQueue&lt;&gt;();
          for (List&lt;String&gt; e : input) {
              if (&quot;Add&quot;.equals(e.get(0))) {
                  Item a = new Item(e.get(1), e.get(2));
                  pq.add(a);
              } else {
                  Item itemAtK = pq.poll();
                  list.add(itemAtK.name);
              }
          }
          return list;
      }
  </code></pre>
  <p><strong>Input :</strong></p>
  <pre><code>Add, Apple, 4
  Add, Ball, 3
  Select, , 
  Add, Toy, 5
  Add, Pen, 1
  Select, , 
  </code></pre>
  <p><strong>Expected Output:</strong></p>
  <pre><code>Ball, Ball
  </code></pre>
  <p><strong>This program gives wrong output:</strong></p>
  <pre><code>Ball, Pen
  </code></pre>