Sắp xếp cuộc gọi
Xem PDF
Đ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 14Output
3
Bình luận
sort tăng dần thời gian bắt đầu cuộc họp trước khi làm nhé mn (dùng kiểu pair và 1 hàm bool để định nghĩa sort)
-
1
VoBaThongL921
5:01 p.m. 9 Tháng 11, 2021
←
đã chỉnh sửa
→
- cơ mà em dùng sort theo first mặc định vẫn ac ạ ;-;
-
1
longkold00
9:26 p.m. 9 Tháng 11, 2021
3 bình luận nữaye! thanks anh nhiều nha bài quy hoạch động đầu tiên em ac được mà ko xem code của editorial luôn :>
thực ra sort mặc định thì nó sẽ sort giá trị fi á :V