Прошёл чемпионат по шагам, он длился несколько дней. За каждый день есть список
записей (userId, steps) — кто сколько прошёл в этот день. Победитель должен
удовлетворять двум условиям:
- участвовал каждый день (есть запись во всех днях);
- среди таких участников набрал наибольшую суммарную сумму шагов за все дни.
Победителей может быть несколько (одинаковая сумма). Нужно вернуть их userId
(в возрастающем порядке) и эту максимальную сумму.
type Entry struct {
UserID int
Steps int
}
type Result struct {
UserIDs []int // возрастающий порядок
Steps int
}
// Champions определяет победителей чемпионата. days[d] — записи за день d.
func Champions(days [][]Entry) Result
Примеры
days = [ [{1,2000},{2,3000}], [{2,2000}] ]
→ {UserIDs: [2], Steps: 5000} // участник 1 пропустил день 2
days = [ [{1,4000},{2,3000}], [{2,8000},{1,7000}] ]
→ {UserIDs: [1,2], Steps: 11000} // оба по 11000
Ограничения
- Дней
0 ≤ D, записей за день 0 ≤ k. В пределах одного дня userId не
повторяются.
steps ≥ 0.- Если победителей нет (нет участника, прошедшего все дни, в том числе когда
дней 0 или какой-то день пуст), верните пустой
UserIDs (nil тоже допустим) и Steps: 0.
- Ожидается O(суммарного числа записей).
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.