Xếp lịch

Đề bài:Cho n công việc. Một công việc thứ i có thời gian bắt đầu là si và thời gian để làm xong là fi. Tìm dãy công việc lớn nhất sao cho hai công việc bất kì không chồng chéo lên nhau (hai công việc không chồng chéo lên nhau nếu thời gian bắt đầu của công việc sau lớn hơn hoặc bằng thời gian kết thúc của công việc trước). Các công việc có thể không tuân theo thứ tự. Dãy công việc dài nhất cũng là dãy công việc thời gian hoàn thành ngắn nhất.
Đầu vào: Một số n là số lượng công việc, dòng tiếp theo chứa n thời gian bắt đầu, dòng tiếp theo chứa n thời gian để hoàn thành công việc đó.
Đầu ra: Dãy công việc lớn nhất có thể hoàn thành.
Độ phức tạp mong muốn: O(nlogn).
Ví dụ:

input:
3
1 2 3
3 3 3
output:
1

Bạn chưa đăng nhập? Đăng nhập để Submit ngay!