Skip to main content

Checkpoint — Ngày bận nhất của quán

Challenge on lesson: Checkpoint — Intervals

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** Quán có n lượt đặt bàn, lượt i từ l_i đến r_i (đóng; l = r cho phép — lượt 0 phút). Quán phục vụ trong ngày [0, D]. Cần thuê tối thiểu bao nhiêu bàn để **một lượt không phải chờ** — bàn kết thúc lúc t có thể nhận lượt bắt đầu tại t? Lượt 0 phút vẫn chiếm một bàn tại đúng khoảnh khắc đó (hai lượt điểm cùng thời điểm cần hai bàn). In số bàn tối thiểu. **Ràng buộc:** 1 ≤ n ≤ 200 000; 0 ≤ D ≤ 10^9; 0 ≤ l ≤ r ≤ D. **Vào:** dòng đầu n D; n dòng: l r. **Ra:** một số — số bàn tối thiểu. **Điểm:** 100. Quét sự kiện với BỨC LOẠI ba lớp tại cùng thời điểm: start-điểm (l = r) đếm trước, rồi end, rồi start-thường — lượt điểm phải hiện diện khoảnh khắc đó, trong khi start-thường tái dụng bàn vừa gỡ.

Back to lesson: Checkpoint — Intervals