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)
Bài này mình sử dụng thuật tham lam thì tất cả đều Ac, tuy nhiên sẽ bị runtime error ở 1 số test lớn, hi vọng ai đó có thể giải đáp giúp mình là vì sao lại như vậy.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.