Masala. N ta gorizontal va vertikal çiziqlar berilgan. Çiziqlarning kesişgan nuqtalarini topiş kerak. Har bir çiziqning çap va öng - boşlaniş va tugaş nuqtalari ma'lum.

Nuqtalar quyidagiça körinişda ifodalangan:

[ [ [1,2], [5,2] ], [ [2,4], [2,8] ], [ [3,1], [9,1] ], [ [4,4], [6,4] ], [ [5,3], [5,6] ], [ [8,0], [8,3] ], [ [9,3], [9,6] ] ]

Uşbu masalani yeçiş usullari ikkita:

• Brute-force algoritmi har bir juft koordinatani tekşirib çiqadi. Işlaş vaqti O(N²).
• Sweep line algoritmi.

Sweep line algoritmi

Dastlab biz gorizontal çiziqlarning boşlaniş va tugaş nuqtalari hamda vertikal çiziqlarning x nuqtalari uçun minimum priority queue'ni işlatamiz.

Keyin Y koordinatalarni binary search tree'ga yiğamiz.

Işlaş tartibi:

1. x-koordinatalarni ösiş tartibida priority queue'ga yiğamiz
2. Agar x-koordinata gorizontal çiziqning boşlaniş nuqtasi bölsa, nuqtaning y-koordinatasini binary search tree'ga qöşamiz
3. Agar x-koordinata gorizontal çiziqning tugaş nuqtasi bölsa, nuqtaning y-koordinatasini binary search tree'dan öçiramiz.
4. Agar nuqta vertikal çiziqqa tegişli bölsa, kesişuv bölişi mumkin. Çiziqning tepa va pastki Y-koordinatalarini olib binary search tree ustida range search amalini bajaramiz. Range search gorizontal liniyani kesgan barça nuqtalarni topib beradi.

Tahlil

Barça kesişuvlarni topiş uçun işlaş vaqti - O(R + N log N). R - barça kesişuvlar soni, N - çiziqlar soni.

• x-koordinatalarni priority queue'ga yiğiş -> O(N log N)
• y-koordinatalarni binary search tree'ga yiğiş -> O(N log N)
• y-koordinatalarni binary search tree'dan öçiriş -> O(N log N)
• binary search tree'da range search - O(R + N log N)

Xulosa. Sweep line algoritmi 2D çiziqlar kesişuvi uçun 1D oraliq qidiruvni qöllaş imkonini beradi.

Kod

Kodda ifodalaş uçun Binary Search tree'dan foydalanmadim, sababi baribir intervyu vaqtida binary search tree API dan foydalaniş imkoni bölmaydi. Şu sababli kod yuqoridagi algoritmdan biroz farq qiladi.

UPDATE: Quyidagi kodda Array.some() hisobiga worst case O(N²) bölib ketadi. Ya'ni quyidagi kod Brute-force metodiga yaqinroq. Quyida tree orqali işlangan variantining linki ham mavjud.

---

Kod Githubda:

Brute-force: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sweep-line/sweep-line.js

Sweep line: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/sweep-line/line-segment-intersection.js

---

Mavzu böyiça savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.