Нужно выбрать день начала отпуска длиной length дней так, чтобы весь отпуск уложился
в ближайшие period дней, а пропущенных встреч было как можно меньше. Дни нумеруются
с 1, первый возможный день отпуска — день 1 (завтра). Отпуск, начавшийся в день x,
занимает дни x, x+1, …, x+length-1, и последний из них не позже дня period.
Календарь задан слайсом days: в день Day назначено Meetings встреч. Порядок
записей произвольный, один день встречается не больше одного раза. Дни после period
на ответ не влияют.
type Day struct {
Day, Meetings int
}
// BestVacation возвращает день начала отпуска и число пропущенных встреч.
// Если оптимальных дней несколько — самый ранний.
func BestVacation(days []Day, period, length int) (start, missed int)
Примеры
BestVacation([]Day{{5, 1}, {6, 3}, {16, 3}, {23, 3}, {30, 1}}, 32, 7)
// 7, 0 — дни 7..13 свободны
BestVacation([]Day{{6, 1}, {7, 3}, {8, 3}, {12, 5}, {16, 2}, {17, 1}, {24, 3}, {28, 3}, {31, 6}}, 34, 14)
// 13, 6 — дни 13..26: встречи 16, 17 и 24
Ограничения: 1 <= length <= period <= 10^6, 0 <= len(days) <= 10^5,
1 <= Day, 0 <= Meetings <= 10^4. Время O(period + len(days)): перебор всех стартов
с пересчётом суммы за O(length) не пройдёт.
Устно: над каждой функцией напишите комментарий со сложностью в формате
// time: O(...), space: O(...). Как решить, если period порядка 10^12, а встреч мало?