Minimum range add operations to get target array

Revision en2, by kazuma_desu, 2017-08-07 09:40:48

Hi! I need some ideas for the following problem.

Given an initial array of zeros and target array, and operation of adding 1 to range [l, r]. Find the minimum number of steps to reach the target array.

I am looking for a solution which is better than O(n^2).

Thanks!

Tags #interview, greedy, array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kazuma_desu 2017-08-07 09:40:48 60
en1 English kazuma_desu 2017-08-07 09:03:55 263 Initial revision (published)