Bubble Cup 13 - Finals [Online Mirror] - problem G

G. Years

Lược dịch: Trong một sứ mệnh du hành vũ trụ, người ta phát hiện bằng chứng đã từng tồn tại nền văn minh ở một hành tinh nọ. Họ may mắn tìm được một quyển sách ghi toàn bộ năm sinh và năm mất của các cư dân đã từng tồn tại trên hành tinh này và điều thú vị là những con số được ghi trong sách đều nằm trong khoảng (1, 10⁹)! Do đó, hành tinh này được gọi là Longlifer.

Để biết nhiều hơn về dân số trong quá khứ của Longlifer, các nhà khoa học cần xác định năm mà có nhiều cư dân còn sống nhất, cũng như dân số của Longlifer vào năm đó. Nhiệm vụ của bạn là giúp các nhà khoa học giải quyết vấn đề này!

Tóm tắt: có N người, mỗi người được xác định bởi 2 chỉ số b (năm sinh) và d (năm mất), b < d. Dựa vào đây, tìm và đưa ra x là năm có nhiều người còn sống nhất và y là dân số năm đó. Nếu có nhiều năm có cùng dân số thì đưa ra năm sớm nhất đạt dân số tối đa.

(Hình minh họa testcase mẫu đầu tiên. Khoảng đỏ là khoảng có dân số đông nhất)

Hướng dẫn giải: Naive method - bài này đơn thuần chỉ là sort và duyệt, không có gì quá cao siêu cả. 

Ta gán nhãn year[i] với ý nghĩa như sau: ban đầu year[i] = 0; với một người được sinh ra vào năm thứ i thì tăng giá trị year[i] lên 1 đơn vị, một người mất đi thì giảm year[i] 1 đơn vị. Nôm na year[i] là số lượng người thêm vào / bớt đi tại mốc thời gian i. Sắp xếp tăng dần i, dùng một biến count để đếm. Kết quả sẽ là max(count) và năm thứ i tương ứng.

Tips: Đối với bài này nên dùng std::map tự sort theo key.

Code mẫu (C++).

Happy coding!