https://www.hackerrank.com/challenges/crush/problem Q: Starting with a 1-indexed array of zeros and a list of operations, for each operation add a “bump-up” value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum in your array.
For example, given array 10 of zeros . Your list of 3 operations is as follows:
Add the values of k between the indices a and b inclusive:
index-> 1 2 3 4 5 6 7 8 9 10
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
The largest value is 10 after all operations are performed.
This (contrived) problem is similar to the skyline problem.
— Solution 1 O(minOf[N+J, J*logJ ] )
Suppose there are J=55 operations. Each operation is a bump-up by k, on a subarray. The subarray has left boundary = a, and right boundary = b.
Step 1: Sort the left and right boundaries. This step is O(N) by counting sort, or O(J logJ) by comparison sort. A conditional implementation can achieve O(minOf[N+J, J*logJ ] )
In the example, after sorting, we get 1 4 5 6 8 9.
Step 2: one pass through the sorted boundaries. This step is O(J).