- Bitta auditoriyada dars o'tkazish uchun n ariza berilsin. Ikki xil fan bir vaqtda ustma-ust tusholmaydi. Har bir arizada darsning boshlanish va tugash vaqtlari ko'rsatilgan (i-chi ariza uchun si va fi). Turli xil arizalar ustma-ust tushishi mumkin va bunda ulardan faqat bittasini qondirish mumkin. Biz har bir arizani [si, fi) oralig'i bilan aniqlaymiz, shunda bitta darsning oxiri boshqa darsning boshiga to'g'ri kelishi mumkin va bu kesishma deb hisoblanmaydi. Rasmiy ravishda aytganda, i va j raqamli arizalar mos keladi (compatible) deyiladi, agar (si, fi) va (sj, fj) intervallar kesishmasa (yoki boshqacha aytganda fl £ sj yoki fj £ si). Arizalarni tanlash vazifasi (activity-selection problem) bir-biriga qo'shilib ketadigan maksimal sonidagi arizalarni to'plashdan iborat.
- xasis algoritm quyidagi tartibda ishlaydi. Faraz qilaylik, arizalar tugash vaqtining o’sishi tartibida saralangan bo’lsin:
- fl £ f 2 £ ... £ fn (1)
Agar bunday bo'lmasa, siz ularni O (n log n) vaqt ichida tartiblashingiz mumkin; bir xil tugash vaqti bo'lgan buyurtmalar tasodifiy tartibda joylashtirilgan. Keyin algoritm quyidagicha ko'rinadi (f va s massiv): - Agar bunday bo'lmasa, siz ularni O (n log n) vaqt ichida tartiblashingiz mumkin; bir xil tugash vaqti bo'lgan buyurtmalar tasodifiy tartibda joylashtirilgan. Keyin algoritm quyidagicha ko'rinadi (f va s massiv):
- Greedy-activity- selector (s, f)
- 1) n = length [s]
- 2) A = {1}
- 3) j = 1
- 4) for i = 2 to n
- 5) Do if si ³ fj
- 6) Then A=A\S’{i}
- 7) j = i
- Return A
Arizalarni tanlash vazifasi
- F to'plami tanlangan arizalarning raqamlaridan iborat, j - ularning oxirgisini raqami; bunda
- • Fj = max {fk : k î A},
- Arizalar dars tugash vaqtini o’sishi tartibida saralangan. Boshlang’ich holatda, A 1 raqamdagi arizani o’zida saqlaydi va j = 1 ni (2-3 qatorlar) o'z ichiga oladi. Shundan so’ng (4-7 qatorlardagi sikl) j raqamli arizaning tugash vaqtidan oldinroq boshlanmaydigan ariza qidiriladi. Agar topilsa, u F to'plamga kiritiladi va j o'zgaruvchisiga uning raqami o’zlashtiriladi (6-7 qatorlar).
- Greedy-activity-selector algoritmi faqat q(n) qadamni talab qiladi (oldindan saralashdan tashqari). Xasis algoritmga muvofiq, har bir qadamda u bo'sh vaqtni maksimal darajada oshirish uchun tanlov qiladi.
Do'stlaringiz bilan baham: |
