Sweep Line

В тази секция ще разгледаме няколко задачи, решавани по "метода на замитащата права" ("Sweep Line"). Идеята на метода се базира на това да се възползваме от факта, че редът, в който изпълняваме зачвките няма значение и можем да го "променим" в по-удобен за нас начин. Обикновено това ни позволява да използваме някаква структура данни, в която да поддържаме информацията, която ни трябва, за отговарянето на "подредените" заявки. Това може драстично да оптимизира алгоритъма, като свежда сложността на части от имплементацията от линейна до логаритмична или дори константна. Този метод е тясно свързан с техниката на "плъзгащия се прозорец", която разгледахме по-рано (а както ще забележите - и задачите са донякъде подобни).

Подходяща тема, която можете да разгледате, е Метод на замитащата права.

Всички задачи включват някакъв вид заявки или обекти/неща, които искаме да изследваме, които няма проблем да сортираме и обходим в желан от наш ред. Какъв е този ред зависи от задача до задача и е нещо, което вие трябва да измислите. Както и при плъзгащия се прозорец, за повечето задачи съществува лесно "наивно" решение, с което можете да тествате бързото си такова.