Test Set 1

Ta có thể giải Test Set này bằng cách thử một cách đơn giản mọi tập con của các hoạt động sẽ được Jamie phụ trách, rồi giao những hoạt động còn lại cho Cameron. Với mỗi tập con, ta kiểm tra từng cặp hoạt động để xem chúng có chồng lấn hay không. Một hoạt động có thời điểm bắt đầu \(s_1\) và thời điểm kết thúc \(t_1\) chồng lấn với một hoạt động khác có thời điểm bắt đầu \(s_2\) và thời điểm kết thúc \(t_2\) nếu giao của hai khoảng thời gian không rỗng, tức là \(\max(s_1,s_2) < \min(t_1,t_2)\).

Thời gian chạy của lời giải này là \(O(2^N \times N^2)\), đủ nhanh để giải Test Set 1.

Test Set 2

Ta có thể giải Test Set này bằng cách tham lam phân công các hoạt động theo thứ tự tăng dần của thời điểm bắt đầu. Với mỗi hoạt động (theo thứ tự đó), ta kiểm tra xem Jamie hoặc Cameron có thể được giao phụ trách hoạt động này hay không, rồi giao nó cho một người có thể nhận (hoặc chọn tùy ý nếu cả hai đều có thể nhận). Việc kiểm tra có thể được thực hiện bằng cách duyệt qua tất cả các hoạt động trước đó đã được giao cho Jamie và Cameron.

Cách phân công tham lam là đúng vì trường hợp duy nhất khiến việc phân công thất bại là có một thời điểm được bao phủ bởi ba hoạt động. Khi đó quả thật không tồn tại cách phân công hợp lệ. Khi quyết định sẽ giao cho ai một hoạt động có thời điểm bắt đầu \(s\), ta mới chỉ phân công những hoạt động có thời điểm bắt đầu không muộn hơn \(s\). Vì vậy, nếu cả Jamie lẫn Cameron đều đã được giao một hoạt động có thời điểm kết thúc muộn hơn \(s\), thì có ba hoạt động cùng bao phủ khoảng thời gian từ \(s\) đến \(s+1\), nên không thể có cách phân công nào. Nếu tồn tại một cách phân công, không thể có một tập gồm ba hoạt động đôi một chồng lấn. Do đó, theo phản đảo của lập luận trước, ở mỗi bước ta sẽ luôn có thể giao hoạt động cho ít nhất một trong hai người Jamie và Cameron.

Thời gian chạy của lời giải này là \(O(N^2)\), đủ nhanh để giải Test Set này. Để tối ưu lời giải xuống \(O(N \log N)\) thời gian, ta có thể kiểm tra hiệu quả một hoạt động có thể được giao cho Jamie hay Cameron hay không bằng cách lưu thời điểm kết thúc của hoạt động cuối cùng đã giao cho mỗi người, rồi so sánh thời điểm đó với thời điểm bắt đầu của hoạt động mới. Khi ấy, sau khi sắp xếp các hoạt động theo thời điểm bắt đầu, ta chỉ cần thêm \(O(N)\) thời gian.

Cách tiếp cận bằng đồ thị

Một cách khác để giải Test Set này là xây dựng một đồ thị gồm \(N\) đỉnh, mỗi đỉnh biểu diễn một hoạt động. Ta thêm một cạnh nối một cặp đỉnh nếu hai hoạt động tương ứng chồng lấn nhau (xem phần Test Set 1 để biết cách kiểm tra hai khoảng có chồng lấn hay không). Đồ thị này thường được gọi là đồ thị khoảng.

Do đó, bài toán tương đương với việc tìm một phép phân hoạch các đỉnh thành hai tập \(C\) và \(J\) sao cho mọi cạnh đều nối một đỉnh thuộc \(C\) với một đỉnh thuộc \(J\): ta có thể giao tất cả hoạt động biểu diễn bởi các đỉnh trong \(C\) cho Cameron và tất cả hoạt động biểu diễn bởi các đỉnh trong \(J\) cho Jamie. Thuật toán tìm phép phân hoạch này (hoặc báo rằng phép phân hoạch không tồn tại) chạy tuyến tính theo kích thước của đồ thị. Đồ thị có \(N\) đỉnh và \(O(N^2)\) cạnh, nên cần \(O(N^2)\) thời gian để xây dựng đồ thị và \(O(N^2)\) thời gian để chạy thuật toán phân hoạch; vì vậy tổng thời gian vẫn là \(O(N^2)\).

Dựa trên phân tích chính thức của Google Code Jam.