Блог пользователя Usu

Maximum number of rectangles which includes a certain point

Автор Usu, история, 7 лет назад, По-английски

Hey! Does anybody have a solution in n log n for this? Given n rectangles, determinate a point which is included by a maximum number of rectangles (including the boundaries).

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +24 Проголосовать: не нравится

It can be solved with sweep line algo and segment tree in $$$O(N \lg N)$$$.

  1. For each rectangle $$$[x_1, x_2] \times [y_1, y_2]$$$, produce two events $$$(x_1, (y_1, y_2), +)$$$ and $$$(x_2, (y_1, y_2), -)$$$.
  2. Sort all the events (there are $$$2N$$$ such many) by $$$x$$$.
  3. From minimum $$$x$$$ to maximum $$$x$$$, if it's from left side of some rectangle ($$$(x_1, (y_1, y_2), +)$$$), add 1 to all the points in the closed interval $$$[y_1, y_2]$$$, otherwise, subtract 1 to those in the closed interval $$$[y_1, y_2]$$$.
  4. After each addition or subtraction, find the maximum value among all possible $$$y$$$ which is a candidate to the answer(update the answer).
  5. Addition/Subtraction on an interval and querying maximum value can be done with segment tree in $$$O(\lg C)$$$ per operation, where $$$C$$$ is the range of values. If we first normalize all the value $$$y$$$, it can be reduced to $$$O(\lg N)$$$.
→ Ответить