14-dars: Intervallar

2-darajaKumush — usullar9–16 darslar

HayotdaMaktab

Aktzalga o’n bitta to’garak yozilgan, har biri o’z vaqtini aytgan. Zal bitta. Direktor eng ko’p to’garakka ruxsat bermoqchi — lekin qaysi birini tanlash kerak? Eng erta boshlanadiganimi, eng qisqasimi, yoki butunlay boshqa mezonmi?

Bu darsdan keyin siz

• intervallarni to’g’ri mezon bo’yicha saralashni tanlaysiz
• eng ko’p to’qnashmaydigan interval masalasini O(n log n) da yechasiz
• noto’g’ri mezon nega yiqilishini misol bilan ko’rsatasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·juftlikda·Qog'oz, chizg'ich va rangli qalam

Qog’ozga 0 dan 12 gacha vaqt chizig’ini chizing. Ustiga oltita to’garakni gorizontal chiziq sifatida joylashtiring — ular kesishsin.

Endi imkon qadar ko’p to’garakni tanlang, ammo tanlanganlar kesishmasin. Sinfdoshingiz ham alohida tanlasin, keyin natijalarni solishtiring. Kim ko’p topdi va qanday qoida bilan tanladi?

Nimani sezishingiz kerak

«Eng erta tugaydiganini ol» degan qoida deyarli har doim g’olib chiqadi. Sabab oddiy: u zalni eng erta bo’shatadi, ya’ni qolganlarga eng ko’p joy qoldiradi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sekin yechim

Ishonchli yo’l — hech narsa taxmin qilmaslik. Intervallarni tugash vaqti bo’yicha saralaymiz va har biri uchun «shu interval bilan tugaydigan eng uzun zanjir qancha?» degan savolga javob beramiz.

sekin.pyNusxalash

1guruhlar = [(0, 3), (1, 5), (3, 6), (4, 8), (6, 8)]2guruhlar.sort(key=lambda x: x[1])3n = len(guruhlar)4dp = [1] * n5for i in range(n):6  for j in range(i):7      if guruhlar[j][1] <= guruhlar[i][0] and dp[j] + 1 > dp[i]:8          dp[i] = dp[j] + 19print(max(dp))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1guruhlar = [(0, 3), (1, 5), (3, 6), (4, 8), (6, 8)]2guruhlar.sort(key=lambda x: x[1])3n = len(guruhlar)4dp = [1] * n5for i in range(n):6  for j in range(i):7      if guruhlar[j][1] <= guruhlar[i][0] and dp[j] + 1 > dp[i]:8          dp[i] = dp[j] + 19print(max(dp))

Sizning bashoratingizTekshirish

Javobni ko'rish

3

Har interval uchun oldingi barcha variantlar ko'rib chiqiladi — shuning uchun bu yechim hech narsani o'tkazib yubormaydi va etalon bo'la oladi. Usulning nomi 26-darsda beriladi.

Nega sekin

Ikkita ichma-ich sikl: n². Chegara esa n ≤ 200000.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 5 000	n = 200 000
Har juftni ko‘rishn^2	10⁶sig‘adi	10⁷sig‘adi	10¹⁰sig‘maydi
Saralash + ochko‘zlikn log n	9 966sig‘adi	61 439sig‘adi	10⁶sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

Tugash vaqti bo’yicha saralaymiz va ro’yxat bo’ylab bir marta yuramiz. Interval oldingisi tugagandan keyin boshlansa — olamiz.

tez.pyNusxalash

1guruhlar = [(0, 3), (1, 5), (3, 6), (4, 8), (6, 8)]2guruhlar.sort(key=lambda x: x[1])3soni = 04oxiri = -15for boshi, tugashi in guruhlar:6  if boshi >= oxiri:7      soni += 18      oxiri = tugashi9print(soni)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1guruhlar = [(0, 3), (1, 5), (3, 6), (4, 8), (6, 8)]2guruhlar.sort(key=lambda x: x[1])3soni = 04oxiri = -15for boshi, tugashi in guruhlar:6  if boshi >= oxiri:7      soni += 18      oxiri = tugashi9print(soni)

Sizning bashoratingizTekshirish

Javobni ko'rish

3

Olinganlar: 0–3, 3–6 va 6–8. Chegarada tegib turish to'qnashuv hisoblanmaydi, shuning uchun >= yozilgan — > bo'lsa javob 2 chiqardi.

Mezon nega aynan tugash vaqti

Boshqa mezonlar tabiiy ko’rinadi, lekin yiqiladi. Buni tekshirish oson: bitta uzun interval hammasini yeb qo’yadigan misol tuzamiz.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1guruhlar = [(0, 10), (1, 2), (3, 4)]2def sanash(tartib):3  soni = 04  oxiri = -15  for boshi, tugashi in tartib:6      if boshi >= oxiri:7          soni += 18          oxiri = tugashi9  return soni10print(sanash(sorted(guruhlar, key=lambda x: x[0])), sanash(sorted(guruhlar, key=lambda x: x[1])))

Sizning bashoratingizTekshirish

Javobni ko'rish

1 2

Boshlanish bo'yicha saralansa, birinchi bo'lib 0–10 olinadi va zal butun kunga band bo'ladi. Tugash bo'yicha saralansa ikkita qisqa interval sig'adi.

◆Asosiy g'oya

Ochko’zlikda mezon tanlash — butun yechim. Bir xil kod ikki xil saralash bilan ikki xil javob beradi, ikkalasi ham xato bermaydi. Shuning uchun mezonni asoslash shart: 16-dars aynan shu haqda.

Sinab ko’r

Vizualda intervallar tugash vaqti bo’yicha saralangan. Har qadamda qaysi biri nega olinganini yoki tashlanganini kuzating.

Intervallar — eng ko'p uchrashuv

Har qator — bitta guruh, ustunlar esa vaqt. Yashil olindi, kulrang tashlandi.

Guruhlar tugash vaqti bo'yicha saralanadi va to'qnashmaydigan birinchi guruh har safar olinadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Beshta guruh, xona bitta. Guruhlar TUGASH vaqti bo'yicha saralangan — yuqoridagisi eng erta bo'shatadi.
2. 0-3 guruhi olinadi — xona bo'sh edi. Endi xona 3 gacha band.
3. 1-5 guruhi tashlanadi: xona 3 gacha band, u esa 1 da boshlanadi.
4. 3-6 guruhi olinadi — xona bo'sh edi. Endi xona 6 gacha band.
5. 4-8 guruhi tashlanadi: xona 6 gacha band, u esa 4 da boshlanadi.
6. 6-8 guruhi olinadi — xona bo'sh edi. Endi xona 8 gacha band.
7. Jami 3 ta guruh sig'di. Ochko'zlik har safar eng erta bo'shatadigan guruhni oldi — nega bu optimal, 16-darsda isbotlanadi.

0-3

1-5

3-6

4-8

6-8

Beshta guruh, xona bitta. Guruhlar TUGASH vaqti bo'yicha saralangan — yuqoridagisi eng erta bo'shatadi.

Ko'rilgan guruh0

OrqagaO‘ynatishOldinga1/7Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

14 / 40

MasalaEng ko'p to'qnashmaydigan intervalni tanlang.

Taklif qilingan yechim

1. 1Intervallarni UZUNLIGI bo‘yicha saralaymiz — qisqasi oldin.
2. 2Ro‘yxat bo‘ylab yuramiz va to‘qnashmaydiganini olamiz.
3. 3Olingan intervalning tugash vaqtini eslab qolamiz.
4. 4Olinganlar sonini chiqaramiz.

Bu javobning 1-qismi noto'g'ri. Qisqa interval har doim ham yaxshi tanlov emas: u ikkita uzunroq intervalning O'RTASIGA tushib, ikkalasini ham buzishi mumkin. Masalan (0,4), (3,5), (4,8) da eng qisqasi (3,5) olinsa javob 1 chiqadi, tugash vaqti bo'yicha esa 2.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Nega aynan tugash vaqti bo'yicha saralanadi?

Javobni ko'rish

Eng erta tugaydigan interval resursni eng erta bo’shatadi, ya’ni qolganlarga eng ko’p imkoniyat qoldiradi. Hech qanday boshqa tanlov bundan ko’proq joy qoldira olmaydi.

2boshi >= oxiri o'rniga boshi > oxiri yozilsa nima o'zgaradi?

Javobni ko'rish

Chegarada tegib turgan intervallar to’qnashgan hisoblanadi va javob kamayadi. Bu shartga bog’liq: masala matnida «tugagan paytda boshlansa bo’ladimi» degan gap albatta bo’ladi.

3Uzunlik bo'yicha saralash nega yiqiladi?

Javobni ko'rish

Qisqa interval ikkita uzunroq intervalning o’rtasiga tushib, ikkalasini ham buzishi mumkin. Bitta qisqa oladi, ikkitasini yo’qotadi.

4oxiri = -1 boshlang'ich qiymati nega xavfsiz?

Javobni ko'rish

Intervallar 0 dan boshlanadi, -1 esa hech qanday haqiqiy vaqtdan kichik. Agar vaqtlar manfiy bo’lishi mumkin bo’lsa, bu qiymatni ham pastroq olish kerak.

5Sekin yechim nega baribir kerak?

Javobni ko'rish

U etalon: ochko’z yechim bilan javoblari solishtiriladi. Mezon xato tanlangan bo’lsa, farq aynan shu solishtirishda chiqadi (15-dars).

Masalalar

Masalalar

3 ta

• Movie FestivalCSES 1629o'rta

  Darsdagi masalaning o‘zi, haqiqiy o‘lchamda.

• Restaurant CustomersCSES 1619oson

  Bu yerda tanlash yo‘q — kelish va ketish hodisalarini alohida saralab, sanab chiqing.

• Room AllocationCSES 1164qiyin

  Bitta zal emas, eng kam nechta zal kerakligi so‘ralgan. Bo‘shagan zalni tez topish uchun tuzilma kerak.

Lokal mashq: mashqlar/14-intervallar/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Bir kunlik sinf jadvalini oling va oltita to’garakning vaqtini yozing, ular kesishsin. Tugash vaqti bo’yicha saralab, eng ko’pini qo’lda tanlang. Keyin boshlanish bo’yicha saralab yana tanlang — javoblar farq qildimi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

14-intervallar masalasini yeching. sekin.py va tez.py javoblarini python mashqlar/tekshir.py 14-intervallar bilan solishtiring.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Masalani o’zgartiring: har intervalning qiymati bor va qiymatlar yig’indisi eng katta bo’lishi kerak. Ochko’zlik hali ham ishlaydimi? Ishlamasa — buzadigan misol keltiring.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim