Skanlayn / Hodisalarni qayta ishlash

Skanerlash usuli

Skanlayn texnikasi (shuningdek hodisalarni qayta ishlash yoki sweep line deb ham ataladi) intervallar, kesmalar, to‘rtburchaklar, geometriya, vaqt jadvali hodisalari bilan ishlaganda yoki biror narsa faqat diskret nuqtalarda o‘zgaradigan har qanday vaziyatda qo‘llaniladigan kuchli algoritmik yondashuvdir. Har bir mumkin bo‘lgan nuqtani tekshirish o‘rniga, biz asosiy ``hodisalar''ni yig‘amiz, ularni saralaymiz va so‘ng chapdan o‘ngga (yoki pastdan yuqoriga) supurishni simulyatsiya qilamiz.

Bu usul keng qo‘llaniladi:

• interval qamrovi va faol intervallar sonini sanash
• kesmalar yoki to‘rtburchaklar kesishmalarini topish
• vaqt jadvali hodisalari (boshlanish/tugash) bilan bog‘liq masalalarni yechish
• intervallar birlashmasini yoki to‘rtburchaklar maydonini hisoblash
• supurish ko‘rsatkichi siljiganda ma’lumot tuzilmalaridagi o‘zgarishlarni qayta ishlash

Asosiy g‘oya: intervallar yoki shakllarni quyidagi ko‘rinishdagi ``hodisalar''ga aylantirish:

• (position, type, data) So‘ng barcha hodisalarni pozitsiya bo‘yicha saralash va hodisalar orasida nima bo‘lishini simulyatsiya qilish.

Misol 1: Eng ko‘p ustma-ust tushadigan intervallar soni

Masala: $n$ ta interval $[l_i, r_i]$ berilgan, istalgan nuqtada ustma-ust tushadigan intervallarning maksimal sonini toping.