Maximum VALUE of interval which overlaps

Question

This is a follow up question to this question:

Maximum no of overlaps of all time intervals

This is a known question of finding the most overlapping intervals given pairs of begin and end times.

I understand how to solve this question. I want to know how to solve a slight variation to the question.. Same question, but instead of just receiving the begin and end times, you also get a value for each pair.

For example, we could say that we ask about a party where each interval is the arrival time and departure time, BUT we now also add the amount of beers the guest is bringing. When the guest leaves, he takes his beers with him. How can I find the maximum overlapping number of beers?

My issue is that when we iterate over the times and just check when a guest is leaving, we don't know how much beer that guest has brought with him since after sorting the times, we don't know which guest is related to that specific time.

A Java or a C# solution would be great

Input example - we get (begin time, end time, value):

(1, 50 , 3) , (3, 4 , 2) , (5, 40 , 3)

Expected output - 6 (because the maximum sum value was 6 between 5 and 40)

Answer 1

For every guest make two pairs:

(arrival time; bottles)
(departure time; - bottles)

Then sort all pairs by time field and traverse sorted list, at every step adding the second field to bottles here.

Max value of bottles here is what you need

P.S. Note that visit of guest with K beers is equivalent to visit of K guests at the same time (every with one beer)