KSAN - Khách sạn
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

An bắt đầu thực hiện công việc kinh doanh của mình. Cậu ta quyết định sẽ mở một khách sạn nhỏ. Cậu ta nhận được N đơn đặt hàng của N khách hàng, khách hàng thứ i có thời điểm đến là Ti và thời gian thuê phòng là Di. Các khách hàng chỉ muốn ở một mình một phòng. An không muốn từ chối bất cứ yêu cầu nào nhưng cũng không muốn xây quá nhiều phòng, vì cậu ta chỉ mới bắt đầu kinh doanh nên kinh phí không có nhiều. Hãy giúp cậu ta tính xem cần xây ít nhất bao nhiêu phòng để có thể phục vụ cho N khách hàng trên.

Dữ liệu vào: dòng đầu tiên chứa một số nguyên dương N - số lượng khách hàng. Dòng thứ 2 chứa N số nguyên dương, số thứ i là thời điểm đến của khách hàng thứ i. Dòng thứ 3 chứa N số nguyên dương, số thứ i là thời gian thuê của khách hàng thứ i.

Dữ liệu xuất: một số nguyên dương duy nhất là số phòng ít nhất cần xây dựng.

Giới hạn:

  • ≤ N ≤ 105
  • ≤ Ti, Di ≤ 109

Ví dụ

  • input
    3
    1 2 3
    3 3 3
    output
    3
  • input
    5
    1 2 3 4 5
    2 3 4 5 6
    output
    3

  

Back to Top