CODEWITHSUNDEEP
algorithmtree
user7350953
user7350953

Reputation:

[Maximum Energy at a particular Interval]

I encountered one interview question.
Given start time and end time and energy transmitted in this duration. I have to find the maximum energy at any instant.
For ex: Given three intervals
(1,5,10)[Start at 1,end at 5 and energy in this time is 10]
(2,7,14)
(6,8,16)
Then maximum energy at any instant is 30 between time 6 to 7.
My Approach: In a way this is interval overlapping problem but i could not crack it because of third parameter(energy).
On research ,I think it can be solved via Interval Tree . I am looking for some approach and PseudoCode.
Thanks!!.

Upvotes: 0

Views: 69

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Suggested O(nlogn) algorithm:

  1. Turn each (start,end,energy) into (start,energy) and (end,-energy) pairs
  2. Sort pairs by the first coordinate (time)
  3. Iterate through the pairs updating the current energy and tracking the maximum

You will need to be careful to decide what to do in the case when an end time matches a start time - does this count as an instantaneously high energy or not?

Upvotes: 1

Related Questions