Код Senior Два указателя обновлено
Выбор друзей на вечеринку
Условие
Каждый друг - пара [зарплата, счастье]. Друг чувствует себя неуютно, если его зарплата более чем вдвое ниже максимальной среди приглашённых. Найди максимальную сумму счастья.
Примеры
chooseFriends([[3, 1], [1, 3], [5, 3]]) // 4
chooseFriends([[2, 3], [3, 1], [4, 3]]) // 7
chooseFriends([]) // 0
Как подойти
После сортировки по зарплате множество допустимых компаний становится непрерывным отрезком - это и есть ключевое наблюдение, превращающее перебор подмножеств в скользящее окно за O(n log n). Сравнение через умножение, а не деление, избавляет от дробей и ошибок округления. Сумма счастья поддерживается инкрементально: добавили правого, вычли выбывших слева.
Подсказки: 3
- Отсортируй по зарплате - тогда подходящие друзья образуют непрерывное окно.
- Условие окна: зарплата левого, умноженная на два, не меньше зарплаты правого.
- Сумму счастья веди инкрементально, не пересчитывая окно заново.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.