Chọn nhiều khoảng thời gian không giao nhau nhất
Một phòng họp nhỏ có nhiều yêu cầu đặt chỗ, mỗi yêu cầu là một khoảng thời gian từ lúc bắt
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Một phòng họp nhỏ có nhiều yêu cầu đặt chỗ, mỗi yêu cầu là một khoảng thời gian từ lúc bắt đầu đến lúc kết thúc. Ta muốn phục vụ được nhiều yêu cầu nhất, nghĩa là chọn ra một tập hợp các yêu cầu mà không hai yêu cầu nào dùng phòng cùng lúc.
Yêu cầu
Cho n khoảng [l, r]. Hai khoảng được coi là không giao nhau khi khoảng này kết thúc trước hoặc đúng lúc khoảng kia bắt đầu, tức r <= s hoặc t <= l; như vậy hai khoảng có thể dùng chung một phòng khi khoảng trước kết thúc đúng vào lúc khoảng sau bắt đầu. Hãy in ra số khoảng nhiều nhất chọn được.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin theo đúng định dạng trên và in ra stdout một số nguyên duy nhất là số khoảng chọn được.
Input
- Dòng 1: số nguyên n (1 <= n <= 8).
- n dòng tiếp theo: hai số nguyên l, r (0 <= l <= r <= 10000).
Output
Một số nguyên duy nhất: số khoảng nhiều nhất có thể chọn.
Ràng buộc
- Chiến lược đúng là quy tắc tham lam theo thời điểm kết thúc: sắp xếp các khoảng theo
r tăng dần (nếu hai khoảng cùng r thì khoảng có l nhỏ hơn đứng trước), rồi duyệt lần lượt, chọn khoảng đầu tiên và sau đó chỉ chọn khoảng có l lớn hơn hoặc bằng thời điểm kết thúc của khoảng đã chọn gần nhất.
- Vì tiêu chí sắp xếp đã ấn định cả khoá chính r và khoá phụ l, thứ tự duyệt là duy
nhất; đáp án là số lượng khoảng chọn được nên không phụ thuộc vào việc chọn khoảng nào trong nhóm giống nhau.
- Mỗi bộ dữ liệu chạy trong 1 giây.
Ví dụ 1
Input
3
1 3
2 4
3 5
Output
2
Ví dụ 2
Input
4
1 2
2 3
3 4
4 5
Output
4
Giải thích
Dữ liệu vào:
Chọn khoảng [1, 3] rồi khoảng [3, 5]: khoảng thứ hai bắt đầu đúng lúc khoảng thứ nhất kết thúc nên hai khoảng dùng chung phòng được. Số khoảng chọn được là 2, do đó in ra 2.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
