Editorial for WC '15 Contest 1 J3 - Jazz Concert
Submitting an official solution before solving the problem yourself is a bannable offence.
This is a basic implementation problem. We want to make the concert as long as possible by picking two of the
How do we find the lengths of the two longest songs? One way is to store all the song lengths into an array and sort the array. If we sort the array in descending order, the two longest lengths will be at the first and second indices of the array (since it's guaranteed that there are at least two songs). If we sort the array in ascending order, the two longest lengths will be at the last and second last indices. Many languages come up with built-in sort functions, so it is a viable way to approach the problem.
However, using arrays and sorting may seem like overkill for just finding the top two elements. As it turns out, we can also solve the problem by processing each song length as we read them in – there is no need to store all of them at once! We keep two variables: the top value (maximum length) we've encountered so far and the second value (next greatest length) we've encountered so far. For every new
Comments