title: Optimization of a hackerrank algorithm
body: <p>I got asked this on hacker rank and I haven't figured out a solution that didn't run out of allotted time.  I used php and allotted time was 9 seconds...</p>
  
  <p>The idea is there are "ticket stalls" with a certain number of tickets, say 9.  Any ticket they sell is priced at the number of tickets that remain, so first ticket would be $9, second $8 etc...</p>
  
  <p>You're given two lines of data, say:</p>
  
  <pre><code>2 4
  1 5
  </code></pre>
  
  <p>The first row contains two numbers: </p>
  
  <ol>
  <li>The number of stalls</li>
  <li>How many tickets are sold</li>
  </ol>
  
  <p>The second line contains a list of how many tickets each stall has initially, so in this case stall 1 has 1 ticket, stall 2 has 5 tickets.</p>
  
  <p>The problem: what is the maximum amount of money you can make selling the given number of tickets?</p>
  
  <p>In this case, you sell four tickets from stall two for a price of 5 + 4 + 3 + 2 = $14</p>
  
  <p>So how do you solve it.  I figured out two ways, both of which ran out of time</p>
  
  <ol>
  <li><p>Load the stall numbers (second line) into an array.  Go through that array N times (the number of tickets to sell) picking the largest number out, adding it on to an aggregator, decreasing that number.  Then you have the total in the aggregator.</p></li>
  <li><p>Load the stall numbers into an array.  Sort the array.  Go backwards through the array and as you do: store that number (current), add it to the aggregator, go to the next value.  If it is the same (current), then add it to aggregator, subtract 1 from it, keep going.  If it is different, go back to the end of the array and start again.  Do that N times (the internal loop, not the external one).</p></li>
  </ol>
  
  <p>The problem: neither one worked.  </p>
  
  <p>Can anyone think of a better solution?</p>