pro.algorithms
Подскажите оптимальный способ, что там ждут в гугле от человека?
https://leetcode.com/discuss/interview-question/1143056/google-interview-question нужно найти положение axis aligned прямоугольника фиксированного размера чтобы он заключал в себе максимальное количество точек. это какая-то классическая задача?
4 ответов
ну например сканлайн по x + (амортизированный в дереве) сканлайн по y за O(n*log n)
Joric
Автор вопроса
ну например сканлайн по x + (амортизированный в де...
точки отсортировать по y и дерево построить по x?
точки отсортировать по y и дерево построить по x?
Двигаем окно шириной width слева направо, поддерживаем дерево на точках в окне, отсортированное по ключу y. Значение - количество точек в [y, y+height]
В геоме все вычислительные задачи классические)
Похожие вопросы
Обсуждают сегодня