Sắp xếp cuộc gọi

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
corona
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một ông chủ có một phòng họp để cho thuê, có \(N\) người đến đặt họp, cuộc họp của người thứ \(i\) bắt đầu tại thời điểm \(a_i\) và kết thúc tại thời điểm \(b_i (a_i<b_i)\). Hai cuộc họp thứ \(i\) và \(j\) có thể cùng xảy ra khi \(b_i \leq a_j\) hoặc \(b_j \leq a_i\). Hãy tính xem ông chủ có thuể cho tối đa bao nhiêu người thuê phòng.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(N (N \leq 5000)\)
  • \(N\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(a_i\) và \(b_i\) là thời gian bắt đầu và kết thúc của cuộc họp thứ \(i\).

Output

  • Một số nguyên duy nhất là số người tối đa có thể thuê phòng.

Example

Test 1

Input 
 4
8 10
10 20
2 3
13 14
Output 
3

Bình luận


  • -8
    IGCONITO    7:33 p.m. 6 Tháng 10, 2020 ← đã chỉnh sửa

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

    • 3 bình luận nữa