Trong một cơ quan hành chính có N nhân sự, mỗi người đang đảm nhiệm một công việc riêng biệt. Mỗi công việc bao gồm một tập hợp các nhiệm vụ con, được biểu diễn bằng các số nguyên dương.
Thực hiện chủ trương sắp xếp tinh gọn lại bộ máy, Ban lãnh đạo phải thực hiên kế hoạch họp nhất theo yêu cầu bằng cách gộp một số đầu việc lại với nhau sao cho một người có thể kiêm nhiệm nhiều công việc cùng lúc.
Tuy nhiên, để đảm bảo tính hiệu quả và tránh chồng chéo, một người sẽ bị tinh giản khi và chỉ khi toàn bộ nhiệm vụ của người đó được thực hiện bao phủ hoàn toàn bởi một người khác, thì người đó mới có thể bị thay thế.
Nói cách khác: nếu người A thực hiện toàn bộ nhiệm vụ của người B (và có thể có thêm) thì người A có thể thay thế người B trong công việc.
Yêu cầu: Hãy xác định số lượng người ít nhất còn lại sau khi thực hiện tinh gọn bộ máy một cách tối ưu, sao cho không ai có thể bị thay thế nhiều hơn một lần.
Một dòng duy nhất là số nguyên — số người còn lại sau khi đã tinh gọn bộ máy tối ưu
Dữ liệu vào Sao chép |
3 3 1 2 3 2 1 4 2 3 5 |
Dữ liệu ra Sao chép |
3 |
Dữ liệu vào Sao chép |
4 3 1 2 3 2 1 2 2 1 3 2 3 4 |
Dữ liệu ra Sao chép |
2 |
(1): Cần giữ lại cả 3 người vì không có người nào có tất cả nhiệm vụ của người khác.
(2): Người 1 có nhiệm vụ {1, 2, 3}, bao phủ người 2 và người 3. Người 4 không bị ai bao phủ nên vẫn giữ lại. → Giữ lại người 1 và người 4 → 2 người.