Ban đầu, mỗi hoạt động của một người buộc người kia chăm em bé trong toàn bộ khoảng đó. Câu hỏi còn lại là chia thời gian không có hoạt động như thế nào.

Test Set 1

Test Set 1 có nhiều nhất hai hoạt động, nên có thể xét trường hợp:

• Nếu chỉ một người có hoạt động, cho người kia chăm một khối liên tục 720 phút chứa hoạt động đó; người có hoạt động chăm 720 phút còn lại. Chỉ cần hai lần đổi ca.
• Nếu mỗi người có một hoạt động, cùng ý tưởng vẫn dùng được. Luôn có cách chia vòng 24 giờ thành hai nửa bằng nhau sao cho hoạt động của Cameron nằm hoàn toàn trong nửa của Jamie và ngược lại. Đáp án vẫn là 2.
• Nếu một người, giả sử Cameron, có hai hoạt động, chúng chia vòng 24 giờ thành hai khe. Jamie phải chăm trong cả hai hoạt động. Nếu một khe rỗng (hai hoạt động sát nhau) hoặc Jamie còn đủ thời gian để lấp trọn một khe, chiến lược chia ngày thành hai nửa vẫn cho đáp án 2. Nếu hai hoạt động quá xa và/hoặc quá dài khiến Jamie không đủ thời gian lấp trọn bất kỳ khe nào, cả hai khe đều phải chứa một đoạn Cameron chăm, tức mỗi khe có một lần đổi Jamie sang Cameron và một lần đổi lại; đáp án là 4.

Việc cài đặt các trường hợp này khá ngắn, nhưng phải tính đúng độ dài khe đi qua nửa đêm. Việc lấp một khe bằng thời gian của cả hai người cũng chỉ cần một đoạn liên tục cho mỗi người, nên không tạo nhiều lần đổi hơn cần thiết.

Test Set 2

Sắp các hoạt động theo thời gian. Để xử lý tự nhiên bước chuyển qua nửa đêm cùng thời gian trước hoạt động đầu và sau hoạt động cuối, thêm một bản sao của hoạt động đầu vào cuối danh sách với thời gian cộng 1440. Khi đó mỗi khoảng giữa hai hoạt động đều có hai hoạt động ở hai đầu. Một số khoảng có độ dài 0 vì hai hoạt động sát nhau; các khoảng còn lại chính là toàn bộ thời gian không có hoạt động.

Với khoảng rỗng, không có quyết định nào, chỉ cần đếm lần đổi mà ranh giới đó tạo ra. Với khoảng có hai đầu buộc khác người chăm, ta phải đi từ người ở đầu trái sang người ở đầu phải, nên ít nhất một lần đổi. Ta luôn đạt đúng một lần: cho người ở đầu trái chăm một phần đầu (có thể rỗng), người ở đầu phải chăm phần cuối (có thể rỗng). Vì vậy không cần quan tâm chi tiết các khoảng khác người; bất kỳ lượng thời gian còn lại của một hoặc cả hai người đều có thể đặt vào đó mà không thêm lần đổi.

Khoảng có hai đầu buộc cùng người cần cân nhắc hơn. Nếu giao toàn bộ khoảng cho người ở hai đầu, không thêm lần đổi. Nếu phải dùng dù chỉ một phút của người kia, ta thêm đúng hai lần đổi; không cần nhiều hơn hai vì có thể gom thời gian của người kia thành một đoạn liên tục.

Ta muốn giữ nguyên càng nhiều khoảng cùng người càng tốt. Mỗi khoảng được giữ tiết kiệm đúng hai lần đổi nhưng tiêu tốn lượng thời gian bằng độ dài của nó trong hạn mức 720 phút của người đó. Vì vậy, với các khoảng có Cameron ở hai đầu, sắp theo độ dài và tham lam lấp các khoảng ngắn nhất bằng thời gian Cameron cho đến khi Cameron không còn đủ thời gian cho khoảng ngắn nhất tiếp theo. Làm tương tự cho Jamie. Mỗi khoảng không lấp trọn theo cách này cộng hai lần đổi. Lập luận trao đổi rất trực tiếp: nếu một nghiệm giữ một khoảng dài nhưng bỏ một khoảng ngắn hơn, đổi hai lựa chọn không tăng thời gian dùng và vẫn tiết kiệm cùng hai lần đổi.

Sau khi xử lý các khoảng cùng người, phần thời gian còn lại của một hoặc cả hai người được đặt an toàn vào các khoảng khác người mà không tạo thêm lần đổi, như đã chứng minh. Tổng hiện tại là đáp án.

Các phép sắp xếp quyết định độ phức tạp: \(O(N\log N)\) với \(N=A_C+A_J\), đủ nhanh cho Test Set 2.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 1C, bài Parenting Partnering; kho Google Coding Competitions (Apache-2.0).