Hi all, I’ve just found this problem on: https://www.programcreek.com/2014/07/leetcode-range-addition-java/
It says: "
Assume you have an array of length n initialized with all 0’s and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.
Return the modified array after all k operations were executed.
"
Now, it gives 2 solutions, one is inefficient and one is optimal. The inefficient one puzzles me:
- he makes an array of operations sorted by their start time, and a min heap of operations sorted by their endtime
- then he iterates that array, for each element looking at the top of the heap thus deciding what is the current answer at that index
Quick question: this inefficient mehod could have real life applications where you are forced by the circumstances to use this array & heap method. I am thinking what if “+” is replaced by a complex operation ? Simply storing the total sum that was added until now is possible because “+” is transitive (& associative & commutative & only needs 2 parameters).
Could you please think of a complex operation that forces you to use the array & heap method, simply because storing how many times it was apply (and its parameters) is not possible/inefficient ?
I am trying to come up with a scenario for an operation that forces us to use the first approach.