Nội dung Bài tập
- Mã:
- LUACHONCV
- Tên:
- Bài toán lựa chọn công việc
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- admin
Bài toán:
Giả sử rằng ta có một tập S = { 1,2,...n} của n công việc sử dụng cùng một tài nguyên, ví dụ như một phòng họp, tại một thời điểm chỉ có một công việc được tiến hành. Các công việc i được bắt đầu tại thời điểm si và kết thúc tại thời điểm fi với si ≤ fi . Nếu được chọn, công việc i sẽ chiếm khoảng thời gian là [si, fi)
Hãy lựa chọn các công việc không mâu thuẫn nhau (nghĩa là các khoảng thời gian sử dụng tài nguyên không giao nhau) sao cho số các công việc được chọn là nhiều nhất.
INPUT:
- Dòng 1 chứa số n (1 ≤ n ≤ 105)
- N dòng tiếp theo chứa thời gian khởi đầu si và thời gian kết thúc fi (1<=i<=n)
OUTPUT: Số lượng công việc nhiều nhất được chọn
Ví dụ:
Input
Output
3
1 2
3 5
2 6
2
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
DHLTNC_CT3_CNP
#include <iostream>#include <algorithm>using namespace std;struct PS{ &n...