Intervallar va sweep line: bronlarni birlashtirish, stollar soni va eng gavjum vaqt

Qisqacha: Interval — boshlanishi va tugashi bor oraliq: bron 12:00–13:30. Interval masalalarining ko'pi bitta qadamdan boshlanadi: boshlanish vaqti bo'yicha saralash. Shundan keyin kesishganlarni birlashtirish, bo'sh vaqtni topish va yangi bronni qo'shish bitta o'tish bilan bajariladi. Bir vaqtda nechta stol kerakligini sweep line topadi: har bron "keldi +1" va "ketdi −1" hodisasiga bo'linadi, hodisalar vaqt bo'yicha saralanib, hisoblagich bilan supuriladi. Hammasi O(n log n).

Bu darsda

• Ikki interval kesishishini bitta shart bilan tekshirasiz va yarim ochiq oraliqning foydasini tushuntira olasiz.
• Kesishgan bronlarni birlashtirasiz, bo'sh vaqtlarni topasiz va yangi bronni tartiblangan ro'yxatga qo'shasiz.
• Bir vaqtda nechta stol kerakligini sweep line bilan, stollarni taqsimlashni heap bilan hisoblaysiz.
• Bitta xonaga eng ko'p bronni greedy bilan sig'dirasiz va O(n²) dan O(n log n) ga o'tishni o'lchab ko'rasiz.

Oldin bilishingiz kerak: Greedy algoritmlar, Priority queue va heap naqshlari, Prefix sum va difference array, Saralash tushunchalari.

1. Nega bu kerak?

«Bahor» zali har kuni 10:00 dan 22:00 gacha ochiq va bronlar ko'payib ketdi. Jasur aka daftarga yozadi, lekin endi uchta savolga qog'ozda javob topolmayapti:

1. 5-stolning bronlari bir-biriga tegib-kesishib ketgan. Stol aslida qachon band, qachon bo'sh?
2. Telefon jiringladi: "Ertaga 13:00–17:00 ga stol bormi?" Yangi bronni ro'yxatga qanday qo'shish kerak?
3. Shanba kuni bir vaqtda eng ko'pi bilan nechta stol band bo'ladi? Ofitsiantlarni shunga qarab chaqirish kerak.

Uchala savol bir xil narsa haqida — vaqt oraliqlari. Bunday masalalar dasturlashda ko'p uchraydi: uchrashuvlar kalendari, server yuklamasi, avtobus jadvali. Ularning deyarli hammasi bitta oddiy hiyladan boshlanadi: avval boshlanish vaqti bo'yicha saralash. Bugun shu hiyla nega ishlashini va undan nimalar chiqishini ko'ramiz.

2. Interval va kesishish

2.1 Yarim ochiq oraliq

Interval (oraliq) — boshlanish va tugash nuqtasi bor bo'lak: [start, end). Bron 12:00–13:30 — mehmon 12:00 da keladi va 13:30 da ketadi.

Qavslarga e'tibor bering: chapda kvadrat [, o'ngda yumaloq ). Bu yarim ochiq oraliq: boshlanish nuqtasi kiradi, tugash nuqtasi kirmaydi. Bu shunchaki matematik odat emas — amaliy qulaylik. 12:00–13:00 va 13:00–14:00 bronlari kesishmaydi: birinchi mehmon ketgan daqiqada ikkinchisi o'tiradi. Ikkalasini bitta stolga berish mumkin. Kursda hamma intervallar shunday bo'ladi.

Vaqtni daqiqalarda saqlash qulay: 12:30 → 12 × 60 + 30 = 750. Sonlarni solishtirish va saralash satrlarnikidan oson.

2.2 Kesishish sharti

Ikki interval qachon kesishadi? Avval teskarisini o'ylaymiz: ular kesishmaydi, agar biri ikkinchisi boshlanmasdan tugasa. Ya'ni a.end <= b.start yoki b.end <= a.start. Buni inkor qilsak — kesishish sharti chiqadi:

const toMin = (hhmm) => {
  const [h, m] = hhmm.split(":").map(Number);
  return h * 60 + m;
};
const toHHMM = (min) =>
  `${String(Math.floor(min / 60)).padStart(2, "0")}:` +
  `${String(min % 60).padStart(2, "0")}`;

const overlaps = (a, b) => a[0] < b[1] && b[0] < a[1];

const lunch = [toMin("12:00"), toMin("13:30")];
const meeting = [toMin("13:00"), toMin("14:00")];
const evening = [toMin("13:30"), toMin("15:00")];
console.log(overlaps(lunch, meeting)); // true
console.log(overlaps(lunch, evening)); // false
console.log(toHHMM(toMin("09:05") + 75)); // 10:20

a[0] < b[1] && b[0] < a[1] — "har biri ikkinchisi tugamasdan boshlanadi". < (qat'iy) — yarim ochiq oraliq tufayli: 13:30 da tugagan va 13:30 da boshlangan bron kesishmaydi. <= yozsangiz, ular kesishgan hisoblanadi va bitta stol bekorga band bo'ladi.

Ikki bronni solishtirish — O(1). n ta bronda hamma juftlarni solishtirsak — O(n²). Bugungi asosiy g'oya shu kvadratdan qutulish.

Tekshirib ko'ring: 10:00–11:00 va 11:00–12:00 bronlari kesishadimi? 10:00–11:00 va 10:59–12:00-chi?

3. Merge intervals: stol qachon band?

3.1 G'oya: saralangan ro'yxatda faqat oxirgisiga qarash

5-stolning bronlari daftarda yozilish tartibida, ya'ni aralash. Kesishganlarini birlashtirib, band bloklar ro'yxatini olmoqchimiz.

Sodda yo'l: har bronni qolganlari bilan solishtirib, kesishganlarini qo'shish va o'zgarish bo'lmaguncha takrorlash. Bu O(n²) yoki undan ham sekin. Saralash esa vaziyatni o'zgartiradi. Bronlar boshlanish vaqti bo'yicha tartiblangan bo'lsa, yangi bron faqat oxirgi band blok bilan kesishishi mumkin. Undan oldingi bloklar allaqachon tugagan: ular oxirgi blokdan oldin boshlangan va undan oldin tugagan.

const toMin = (s) => Number(s.slice(0, 2)) * 60 + Number(s.slice(3));
const pad = (x) => String(x).padStart(2, "0");
const toHHMM = (m) => `${pad(Math.floor(m / 60))}:${pad(m % 60)}`;

function mergeIntervals(list) {
  const sorted = list.toSorted((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of sorted) {
    const last = merged.at(-1);
    if (last && start <= last[1]) {
      last[1] = Math.max(last[1], end); // kesishadi — cho'zamiz
    } else {
      merged.push([start, end]); // yangi band blok
    }
  }
  return merged;
}

const table5 = [
  ["18:00", "20:00"], ["12:00", "13:30"], ["10:00", "11:00"],
  ["13:00", "14:00"], ["19:00", "21:00"], ["10:30", "11:30"],
  ["16:00", "17:00"],
].map(([s, e]) => [toMin(s), toMin(e)]);

for (const [s, e] of mergeIntervals(table5)) {
  console.log(`${toHHMM(s)}–${toHHMM(e)}`);
}

Konsolda:

10:00–11:30
12:00–14:00
16:00–17:00
18:00–21:00

merged.at(-1) — massivning oxirgi elementi (at). last[1] = … blokning tugashini o'zgartiradi. Bu xavfsiz: merged ichidagi massivlarni o'zimiz yasadik, kirish ma'lumotiga tegmaymiz. toSorted ham asl ro'yxatni o'zgartirmaydi (toSorted).

Birlashtirish shartida <= turibdi, kesishish shartidagi kabi < emas. Sababi: bu yerda biz "stol band bo'lgan uzluksiz vaqt"ni qidiryapmiz. 12:00–13:30 va 13:30–15:00 bitta uzluksiz band blok bo'ladi — oraliqda bo'sh daqiqa yo'q.

3.2 Qadamma-qadam

Yuqoridagi stol bronlarini kuzating. Yuqori qator — saralangan bronlar, pastki qator — band bloklar:

3.3 Murakkablik

Saralash — O(n log n), bitta o'tish — O(n). Jami O(n log n): saralash hal qiladi. Qo'shimcha xotira — natija va saralangan nusxa uchun O(n).

Bronlar allaqachon saralangan holda kelsa (masalan, bazadan ORDER BY start bilan), saralash qadami kerak emas va algoritm O(n) bo'ladi.

4. Yangi bronni qo'shish

Jasur aka telefonda: "13:00–17:00 ga stol bormi?" 5-stolning band bloklari allaqachon saralangan va kesishmaydi. Yangi bronni qo'shib, ro'yxatni yana shu holatda saqlashimiz kerak. Hammasini qayta saralash shart emas — ro'yxat uch qismga bo'linadi:

function insertBooking(busy, booking) {
  const result = [];
  let [start, end] = booking;
  let i = 0;
  // 1) yangi brondan butunlay oldin tugaganlar
  while (i < busy.length && busy[i][1] < start) {
    result.push(busy[i++]);
  }
  // 2) kesishganlar — yangi bron bilan birlashadi
  while (i < busy.length && busy[i][0] <= end) {
    start = Math.min(start, busy[i][0]);
    end = Math.max(end, busy[i][1]);
    i++;
  }
  result.push([start, end]);
  // 3) keyin boshlanadiganlar
  while (i < busy.length) result.push(busy[i++]);
  return result;
}

// 5-stolning band bloklari (soat), yangi bron 13:00–17:00
const busy = [[10, 11.5], [12, 14], [16, 17], [18, 21]];
console.log(insertBooking(busy, [13, 17]));
console.log(insertBooking(busy, [14.5, 15.5]));

Konsolda:

[ [ 10, 11.5 ], [ 12, 17 ], [ 18, 21 ] ]
[ [ 10, 11.5 ], [ 12, 14 ], [ 14.5, 15.5 ], [ 16, 17 ], [ 18, 21 ] ]

Bu misolda o'qish oson bo'lsin deb vaqtni soatlarda yozdik: 11.5 — 11:30. Birinchi chaqiruvda 13:00–17:00 ikki blokni (12:00–14:00 va 16:00–17:00) "yutib", bitta 12:00–17:00 blokka aylandi. Ikkinchisida 14:30–15:30 hech narsa bilan kesishmadi — o'z joyiga tushdi.

Uch qism: avval yangi brondan oldin tugaganlar o'zgarishsiz o'tadi, keyin kesishganlar yangi bron bilan birlashadi, so'ng qolganlari o'zgarishsiz qo'shiladi. Har blok bir marta ko'riladi — O(n).

Joyni topishni ikkiga bo'lib qidirish bilan O(log n) ga tezlashtirish mumkin. Lekin yangi massivni yasash baribir O(n). Shuning uchun amalda ko'pincha shu oddiy O(n) varianti ishlatiladi.

Tekshirib ko'ring: insertBooking([[10, 12], [14, 16]], [12, 14]) nima qaytaradi?

5. Bir vaqtda nechta stol kerak?

5.1 Sodda yechim

Shanba kungi zal bronlarini olamiz. Bir vaqtda eng ko'p band stollar soni — eng ko'p kesishma. Sodda kuzatuv: band stollar soni faqat kimdir kelganda oshadi. Demak, eng ko'p qiymat qaysidir bronning boshlanish daqiqasida bo'ladi. Har bron boshlanishida nechta bron davom etayotganini sanaymiz: n ta boshlanish × n ta bron — O(n²).

5.2 G'oya: vaqt chizig'i bo'ylab supurish

Vaqt chizig'ini tasavvur qiling: chapda 10:00, o'ngda 22:00. Unga tik chiziq — "hozir" chizig'ini qo'yamiz va uni chapdan o'ngga suramiz. Chiziq bron boshiga tegsa — band stollar +1, bron oxiriga tegsa — −1. Bu usul sweep line (supuruvchi chiziq) deb ataladi.

Amalda chiziqni har daqiqaga surmaymiz — faqat hodisalar bo'yicha sakraymiz. Har bron ikki hodisa beradi: [start, +1] va [end, -1]. Hodisalarni vaqt bo'yicha saralab, hisoblagichni yuritamiz:

const toMin = (s) => Number(s.slice(0, 2)) * 60 + Number(s.slice(3));
const pad = (x) => String(x).padStart(2, "0");
const toHHMM = (m) => `${pad(Math.floor(m / 60))}:${pad(m % 60)}`;

function maxTables(bookings) {
  const events = [];
  for (const [start, end] of bookings) {
    events.push([start, +1], [end, -1]); // keldi / ketdi
  }
  // vaqt bo'yicha; tenglikda avval ketganlar (-1)
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let current = 0;
  let best = 0;
  let bestTime = null;
  for (const [time, delta] of events) {
    current += delta;
    if (current > best) {
      best = current;
      bestTime = time;
    }
  }
  return { best, bestTime };
}

const day = [
  ["10:00", "12:00"], ["11:00", "13:00"], ["12:00", "14:00"],
  ["12:30", "13:30"], ["13:00", "15:00"], ["18:00", "20:00"],
  ["18:30", "21:00"], ["19:00", "22:00"],
].map(([s, e]) => [toMin(s), toMin(e)]);

const { best, bestTime } = maxTables(day);
console.log(`${best} ta stol, birinchi marta ${toHHMM(bestTime)} da`);

a[0] - b[0] || a[1] - b[1] — avval vaqt bo'yicha. Vaqt teng bo'lsa (0 — falsy), || ikkinchi qoidaga o'tadi: −1 (ketish) +1 (kelish) dan oldin. Bu yarim ochiq oraliqning sweep line dagi ko'rinishi: 12:00 da ketgan mehmonning stoli 12:00 da kelganga beriladi.

Hodisalarni birma-bir kuzating — pastda hisoblagichlar:

5.3 O'lchov

Sweep line'da 2n hodisani saralash — O(n log n), o'tish — O(n). Jami O(n log n), xotira O(n). Sodda yechim — O(n²). Ikkalasini bir xil bronlarda benchmarking darsidagi usulda o'lchadik: har n alohida jarayonda, isitish, mediana; raqamlar taxminiy. Bronlar urug'li generator bilan yasaldi: 10:00–21:00 oralig'ida boshlanadi, 30–180 daqiqa davom etadi.

Sodda yechimda n ikki baravar oshsa, vaqt to'rt baravar oshadi. Sweep line'da esa taxminan ikki baravar. 16 000 bronda farq 400 baravar. Sweep line bilan 1 million bron ham bir soniyadan kam vaqtda hisoblandi:

Nisbatlar ×1,7, ×1,9, ×2,0 — n log n uchun kutilgandek (log n juda sekin o'sadi).

5.4 Muqobil: daqiqalar bo'yicha difference array

«Bahor»da vaqt cheklangan: 10:00 dan 22:00 gacha — atigi 720 daqiqa. Bunday holatda saralashsiz ham bo'ladi. Difference array yasaymiz: diff[start]++ va diff[end]--, keyin prefiks yig'indi har daqiqadagi band stollar sonini beradi. Vaqt — O(n + T), T — daqiqalar soni (720). Bu usulni 3-mashqda "aniq to'g'ri" yechim sifatida ishlatamiz.

Qachon qaysi biri? Vaqt oralig'i kichik va butun sonli bo'lsa (daqiqa, kun) — difference array. Vaqt cheksiz yoki kasr bo'lsa (millisekundlar, yillar) — sweep line.

6. Qaysi bron qaysi stolga?

Sweep line stollar sonini aytadi, lekin qaysi mehmon qaysi stolga o'tirishini aytmaydi. Buning uchun Priority queue va heap naqshlari darsidagi g'oya kerak. Bronlarni boshlanish bo'yicha olamiz va band stollarni tugash vaqti bo'yicha min-heap'da saqlaymiz. Har yangi bronda faqat bitta savol: "Eng erta bo'shaydigan stol shu paytgacha bo'shaganmi?" Ha — o'sha stolni beramiz. Yo'q — yangi stol ochamiz.

class MinHeap {
  #items = [];
  get size() { return this.#items.length; }
  peek() { return this.#items[0]; }
  push(x) {
    const a = this.#items;
    a.push(x);
    let i = a.length - 1;
    while (i > 0 && a[(i - 1) >> 1][0] > a[i][0]) { // ota kattaroq
      [a[i], a[(i - 1) >> 1]] = [a[(i - 1) >> 1], a[i]];
      i = (i - 1) >> 1;
    }
  }
  pop() {
    const a = this.#items;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

function assignTables(bookings) {
  const order = bookings.toSorted((a, b) => a.start - b.start);
  const busy = new MinHeap(); // [tugash vaqti, stol raqami]
  let tables = 0;
  const plan = [];
  for (const b of order) {
    let table;
    if (busy.size && busy.peek()[0] <= b.start) {
      table = busy.pop()[1]; // eng erta bo'shagan stol
    } else {
      table = ++tables; // yangi stol ochamiz
    }
    busy.push([b.end, table]);
    plan.push(`${b.guest} → ${table}-stol`);
  }
  return { tables, plan };
}

const h = (s) => Number(s.slice(0, 2)) * 60 + Number(s.slice(3));
const result = assignTables([
  { guest: "Dilshod aka", start: h("12:00"), end: h("14:00") },
  { guest: "Malika", start: h("11:00"), end: h("13:00") },
  { guest: "Bobur", start: h("12:30"), end: h("13:30") },
  { guest: "Jasur aka", start: h("13:00"), end: h("15:00") },
  { guest: "Sardor", start: h("14:00"), end: h("15:00") },
]);
console.log(result.tables);
console.log(result.plan.join("\n"));

Konsolda:

3
Malika → 1-stol
Dilshod aka → 2-stol
Bobur → 3-stol
Jasur aka → 1-stol
Sardor → 3-stol

MinHeap — Heap darsidagi kabi massivdagi binar heap. Bu yerda u [tugash, stol] juftlarini birinchi element bo'yicha tartiblaydi. (i - 1) >> 1 — otaning indeksi: >> 1 ikkiga bo'lib, kasrni tashlaydi (bitwise operatorlar). Jasur aka 13:00 da kelganda heap tepasida Malikaning stoli turibdi (13:00 da bo'shaydi) — uni oldi.

Murakkablik: saralash O(n log n), har bron uchun heap amali O(log n). Jami O(n log n), heap xotirasi — O(stollar soni).

7. Bitta xonaga eng ko'p bron

«Bahor»da bitta VIP xona bor. Bir kunda unga sakkizta so'rov keldi va ba'zilari kesishadi. Eng ko'p sonli bronni qabul qilish kerak (davomiyligi muhim emas). O'tgan darsda shu masalani greedy bilan yechishni va'da qilgan edik.

Qaysi mezon bo'yicha ochko'z bo'lish kerak? "Eng erta boshlanadigan" — adashadi: 10:00–16:00 so'rovi kunni yeydi. "Eng qisqasi" — u ham adashadi. To'g'ri mezon — eng erta tugaydigan: xonani imkon qadar tez bo'shatadi va keyingilarga ko'proq joy qoldiradi.

function maxBookings(bookings) {
  const byEnd = bookings.toSorted((a, b) => a[1] - b[1]);
  const chosen = [];
  let freeFrom = -Infinity; // xona qachondan bo'sh
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) { // eng erta tugaydiganini olamiz
      chosen.push([start, end]);
      freeFrom = end;
    }
  }
  return chosen;
}

// VIP xonaga so'rovlar (soat)
const requests = [[10, 16], [11, 12], [12, 14], [13, 15], [14, 17],
  [16, 18], [18, 22], [19, 20]];
console.log(maxBookings(requests));

Konsolda:

[ [ 11, 12 ], [ 12, 14 ], [ 14, 17 ], [ 19, 20 ] ]

To'rtta bron qabul qilindi. Almashtirish dalili: eng yaxshi javobda birinchi bron boshqa bo'lsin deylik. Uni eng erta tugaydiganiga almashtiramiz. U boshqasidan kech tugamaydi, shuning uchun keyingi bronlarga xalaqit bermaydi. Bronlar soni o'zgarmaydi — demak, greedy tanlov bilan ham eng yaxshi javob bor.

Murakkablik: saralash O(n log n), o'tish O(n). Bu masala activity selection (faoliyatlarni tanlash) nomi bilan klassik — greedy darsliklarning birinchi misoli.

Tekshirib ko'ring: So'rovlar: 10–13, 12–14, 13–15. maxBookings nechta bronni qabul qiladi va qaysilarini?

8. Chegaraviy holatlar

• Bronsiz kun. mergeIntervals([]) — [], maxTables([]) — { best: 0, bestTime: null }. Natijani ekranga chiqarishdan oldin bestTime ni null ga tekshiring.
• Bitta bron. Birlashtirish uni o'zgartirmaydi, stollar — 1.
• Tegib turgan bronlar (12:00–13:00 va 13:00–14:00). Kesishmaydi, bitta stol yetadi. Lekin band blok sifatida — bitta uzluksiz blok. Har funksiya qaysi ma'noni tanlaganini izohda yozing.
• Biri ikkinchisining ichida (10:00–16:00 va 11:00–12:00). Birlashtirishda Math.max(last[1], end) kerak. Faqat end ni yozsangiz, 10:00–12:00 qoladi va blokning oxiri yo'qoladi.
• Bir xil bronlar. Ikki mehmon aynan 12:00–13:00 — sweep line 2 deydi, to'g'ri.
• Noto'g'ri bron (end <= start). Algoritmlar buni kutmaydi. Ma'lumotni kirishda tekshiring — bu forma validatsiyasining ishi.

9. Ko'p uchraydigan xatolar

9.1 Saralashni unutish

mergeIntervals saralashsiz ham ba'zan to'g'ri ishlaydi — bronlar tasodifan tartibda kelsa. Testda bronlarni aralash tartibda bering. Tuzatish: saralash — birinchi qator, hech qachon "ehtiyot uchun olib tashlanmaydi".

9.2 Tenglikda noto'g'ri tartib

Hodisalarni faqat vaqt bo'yicha saralasangiz, 12:00 da kelish va ketish tasodifiy tartibda turadi. Kelish oldin kelsa, hisoblagich bir lahzaga 1 ga oshib ketadi va "4 ta stol kerak" degan noto'g'ri javob chiqadi. Tuzatish: ikkinchi kalit — a[1] - b[1], ya'ni −1 oldin.

9.3 < va <= ni aralashtirish

Kesishish sharti, birlashtirish sharti va tenglik qoidasi bir-biriga mos bo'lishi kerak. Biri yarim ochiq, boshqasi yopiq oraliqqa yozilsa, xato faqat tegib turgan bronlarda chiqadi — ya'ni kamdan-kam va topish qiyin. Tuzatish: bitta qoida tanlang ([start, end)) va uni tegib turgan bronlar testi bilan qo'riqlang.

9.4 Kirishni o'zgartirib yuborish

list.sort() asl massivni saralaydi, last[1] = … esa kirishdagi massiv bo'lsa, uni ham o'zgartiradi. Chaqiruvchi o'z ro'yxati "o'zgarib ketganini" keyin bilib qoladi. Tuzatish: toSorted va merged.push([start, end]) — yangi massivlar.

10. Mashqlar

1-mashq (oson): Qo'lda supuring

Ikki bron: 10:00–12:00 va 12:00–13:00. Ular kesishadimi? Javob: [:yo'q]. Endi uchta bron: 10:00–12:00, 11:00–13:00, 12:00–14:00. Shu bronlar uchun hodisalarni yozib, hisoblagichni qo'lda yuriting. Bir vaqtda eng ko'pi bilan nechta stol kerak? Javob: [:2].

2-mashq (o'rta): Bo'sh vaqtlar

Funksiya freeSlots(bookings, open, close) stolning bo'sh oraliqlarini qaytarsin. bookings — aralash tartibdagi bronlar, open va close — ish vaqti. Ishora: saralang va "shu vaqtgacha hammasi ko'rib chiqildi" degan cursor ni yuriting. Keyingi bron cursor dan keyin boshlansa — orada bo'shliq bor.

function freeSlots(bookings, open, close) {
  const sorted = bookings.toSorted((a, b) => a[0] - b[0]);
  const free = [];
  let cursor = open; // shu vaqtgacha hammasi ko'rib chiqildi
  for (const [start, end] of sorted) {
    if (start > cursor) free.push([cursor, start]); // bo'shliq
    cursor = Math.max(cursor, end);
  }
  if (cursor < close) free.push([cursor, close]);
  return free;
}

const table5 = [[18, 20], [12, 13.5], [10, 11], [13, 14], [19, 21],
  [10.5, 11.5], [16, 17]];
console.log(freeSlots(table5, 10, 22));
console.log(freeSlots([], 10, 22)); // [ [ 10, 22 ] ]

[ [ 11.5, 12 ], [ 14, 16 ], [ 17, 18 ], [ 21, 22 ] ]
[ [ 10, 22 ] ]

3-mashq (qiyin): Sweep line'ni daqiqalar bilan tekshiring

kurs/mashqlar/14/55-intervallar/stollar.test.mjs faylida ikki funksiyani yozing. maxTables(bookings) — sweep line, faqat sonni qaytaradi. maxTablesByMinute(bookings) — difference array, 10:00–22:00 oralig'ida har daqiqani sanaydi. Ikkinchisi sodda, uni aniq to'g'ri deb hisoblaymiz. Testlar:

1. Tegib turgan bronlar (10:00–12:00 va 12:00–13:00) — 1 ta stol.
2. Chegaraviy: bronsiz kun — 0, kun bo'yi bitta bron — 1.
3. Urug'li generator bilan 300 ta tasodifiy kun (har biri 0–14 bron, 30 daqiqalik qadam): ikki funksiya javobi bir xil.

// kurs/mashqlar/14/55-intervallar/stollar.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function maxTables(bookings) {
  const events = [];
  for (const [start, end] of bookings) {
    events.push([start, +1], [end, -1]);
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let current = 0;
  let best = 0;
  for (const [, delta] of events) {
    current += delta;
    best = Math.max(best, current);
  }
  return best;
}

// Sekin, lekin aniq: har daqiqani alohida sanaymiz
function maxTablesByMinute(bookings, open = 600, close = 1320) {
  const diff = Array(close - open + 1).fill(0);
  for (const [start, end] of bookings) {
    diff[start - open]++; // shu daqiqadan band
    diff[end - open]--; // shu daqiqadan bo'sh
  }
  let current = 0;
  let best = 0;
  for (const d of diff) {
    current += d;
    best = Math.max(best, current);
  }
  return best;
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

test("tegib turgan bronlar bitta stolga sig'adi", () => {
  assert.equal(maxTables([[600, 720], [720, 780]]), 1);
});

test("chegaraviy: bronsiz kun — 0, bitta bron — 1", () => {
  assert.equal(maxTables([]), 0);
  assert.equal(maxTables([[600, 1320]]), 1);
});

test("300 ta tasodifiy kun: hodisalar = har daqiqa", () => {
  const random = makeRandom(56);
  for (let k = 0; k < 300; k++) {
    const count = random() % 15;
    const bookings = Array.from({ length: count }, () => {
      const start = 600 + 30 * (random() % 23); // 30 daq.
      const len = 30 * (1 + random() % 6);
      return [start, Math.min(1320, start + len)];
    });
    assert.equal(maxTables(bookings), maxTablesByMinute(bookings));
  }
});

✔ tegib turgan bronlar bitta stolga sig'adi (0.7633ms)
✔ chegaraviy: bronsiz kun — 0, bitta bron — 1 (0.1316ms)
✔ 300 ta tasodifiy kun: hodisalar = har daqiqa (9.4087ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 15.884

4-mashq: Amaliy tajriba — interval qatorlari

kurs/mashqlar/14/MURAKKABLIK.md ga bugungi qatorlarni qo'shing: kesishish (bir juft), merge, insert, bo'sh vaqtlar, stollar soni (sodda, sweep line, difference array), stollarni taqsimlash (heap), VIP xona (greedy). Sweep line uchun o'zingizning o'lchovingizni ham yozing: benchmarking darsidagi kichik o'lchov funksiyangiz bilan (isitish, bir necha o'lchov, mediana) n = 2 000 … 16 000.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Ikki bron kesishadimi | shart | O(1) | O(1) |
| Band bloklar | saralash + o'tish | O(n log n) | O(n) |
| Yangi bron qo'shish | uch qism | O(n) | O(n) |
| Bo'sh vaqtlar | saralash + cursor | O(n log n) | O(n) |
| Stollar soni | har boshlanishda sanash | O(n²) | O(1) |
| Stollar soni | sweep line | O(n log n) | O(n) |
| Stollar soni | difference array | O(n + T) | O(T) |
| Stollarni taqsimlash | saralash + heap | O(n log n) | O(n) |
| VIP xona | greedy (erta tugash) | O(n log n) | O(n) |

git add 14/MURAKKABLIK.md 14/55-intervallar
git commit -m "14/55: intervallar — sweep line va daqiqalar stress testi"

11. Real ishda

• Kalendarlar. Google Calendar va Outlook'dagi "bo'sh vaqtni topish", uchrashuvlar ustma-ust tushganda ogohlantirish — merge va free slots.
• Bron tizimlari. Mehmonxona, shifokor qabuli, stadion — bronni saqlashdan oldin kesishishni tekshirish. Backend'da bu ma'lumotlar bazasi so'rovi bo'ladi. PostgreSQL'da hatto maxsus oraliq turlari va "kesishmasin" cheklovi bor. Uni ma'lumotlar bazasi qismida o'rganamiz.
• Server yuklamasi. "Bir vaqtda nechta foydalanuvchi onlayn edi?" — kirish va chiqish hodisalari bo'yicha sweep line. Grafana kabi monitoring vositalari shunday grafiklar chizadi.
• Grafika va geometriya. To'rtburchaklar kesishishi, xaritada obyektlar ustma-ust tushishi — sweep line ikki o'lchamda.
• Intervyu. "Merge Intervals" (56), "Insert Interval" (57), "Meeting Rooms II" va "Non-overlapping Intervals" (435) — eng mashhur interval savollari. Birinchi qadam deyarli doim bir xil: "Avval saralayman — nima bo'yicha?"

Xulosa

• Interval — [start, end), yarim ochiq: tegib turgan bronlar kesishmaydi. Kesishish: a[0] < b[1] && b[0] < a[1].
• Boshlanish bo'yicha saralash merge va bo'sh vaqtlarni bitta o'tishga aylantiradi: faqat oxirgi blok bilan solishtiriladi — O(n log n).
• Sweep line: har bron — +1 va −1 hodisa, tenglikda avval −1. O'lchovda 16 000 bronda sodda yechim 4,6 s, sweep line 11 ms oldi.
• Vaqt oralig'i kichik bo'lsa — difference array, O(n + T). Stollarni taqsimlash — tugash vaqti bo'yicha min-heap.
• Bitta xonaga eng ko'p bron — eng erta tugaydiganini olish (activity selection, greedy).

Keyingi dars: Masala yechish jarayoni — notanish masala oldida qotib qolmaslik uchun tizimli yo'l: tushunish, misollar, reja, kod va tekshirish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 15.1 (activity selection), 6-bob (heap).
• M. de Berg va boshq., "Computational Geometry: Algorithms and Applications", 3-nashr, Springer, 2008 — 2-bob (sweep line g'oyasi).
• MDN: Array.prototype.toSorted(), Array.prototype.at() — developer.mozilla.org
• LeetCode masalalari (shartlarini o'zingiz o'qing): 56 "Merge Intervals", 57 "Insert Interval", 435 "Non-overlapping Intervals", 253 "Meeting Rooms II" (premium).