Максимальное значение интервала, который перекрывается

Question

Это дополнительный вопрос к этому вопросу:

Максимальное количество перекрытий всех интервалов времени

Это известный вопрос о нахождении наиболее перекрывающихся интерваловзаданные пары времени начала и окончания.

Я понимаю, как решить этот вопрос.Я хочу знать, как решить небольшую вариацию вопроса. Тот же вопрос, но вместо того, чтобы просто получать время начала и окончания, вы также получаете значение для каждой пары.

Например, мы можем сказать, что мы спрашиваем о вечеринке, где каждый интервал - это время прибытия и время отъезда, НО теперь мы также добавляем количество пива, которое приносит гость.Когда гость уходит, он берет свое пиво с собой.Как я могу найти максимальное перекрывающееся количество пива?

Моя проблема в том, что, когда мы повторяем время и просто проверяем, когда гость уходит, мы не знаем, сколько пива принес этот гость с собой.поскольку после сортировки времени мы не знаем, какой гость связан с этим конкретным временем.

Было бы неплохо Java или C # решение

Пример ввода - мы получаем (время начала,время окончания, значение):

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

Ожидаемый результат - 6 (потому что максимальная суммазначение было 6 между 5 и 40)

Answer 1

Для каждого гостя составьте две пары:

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

Затем отсортируйте все пары по полям времени и отсортированному списку перемещения, на каждом шаге добавляя второе поле к bottles here.

Максимальное значение bottles here - это то, что вам нужно

PS Обратите внимание, что посещение гостя с K пивом эквивалентно посещению K гостей одновременно (каждый с одним пивом)