Số phòng họp tối thiểu cần dùng
Một công ty nhận được nhiều yêu cầu đặt phòng họp, mỗi yêu cầu là một khoảng thời gian 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 công ty nhận được nhiều yêu cầu đặt phòng họp, 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. Cần biết phải mở ít nhất bao nhiêu phòng để phục vụ hết mà không hai cuộc họp nào trùng giờ trong cùng một phòng.
Yêu cầu
Cho n cuộc họp, cuộc họp thứ i diễn ra trong khoảng [l, r] với l < r. Hãy in ra số phòng ít nhất cần dùng. Hai cuộc họp dùng chung một phòng được khi khoảng thời gian của chúng không chồng lên nhau theo nghĩa cuộc trước kết thúc trước hoặc đúng lúc cuộc sau bắt đầu.
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ố phòng ít nhất.
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ố phòng ít nhất cần dùng.
Ràng buộc
- Quy tắc tham lam dùng cho bài này: gom 2n mốc thời gian (mỗi cuộc họp đóng góp mốc bắt
đầu l và mốc kết thúc r), sắp xếp tăng dần theo thời điểm. Tại cùng một thời điểm, mốc kết thúc được xử lý trước mốc bắt đầu, nên một cuộc họp bắt đầu đúng lúc cuộc trước kết thúc sẽ tái sử dụng phòng đó. Số phòng cần là số cuộc họp đang diễn ra lớn nhất trong suốt quá trình quét.
- Quy ước trên là duy nhất, nên đáp án không phụ thuộc vào thứ tự các cuộc họp trong dữ
liệu vào.
- 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
1
Giải thích
Dữ liệu vào:
Tại thời điểm 2, hai cuộc họp [1, 3] và [2, 4] đang diễn ra nên cần 2 phòng; cuộc [3, 5] có thể vào lại phòng vừa xong. Vậy đáp án là 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.
