Phân tích: Train Timetable

Bài toán này có thể được giải quyết bằng chiến thuật tham lam. Cách đơn giản nhất để thực hiện việc này là quét qua danh sách tất cả các chuyến đi, được sắp xếp theo thời gian khởi hành, và theo dõi tập hợp các đoàn tàu sẽ có sẵn tại mỗi ga, cũng như thời điểm chúng sẵn sàng để thực hiện một chuyến đi mới.

Khi chúng ta xem xét một chuyến đi, chúng ta kiểm tra xem có đoàn tàu nào sẵn sàng tại ga khởi hành vào thời điểm khởi hành hay không. Nếu có, chúng ta sẽ lấy đoàn tàu đó ra khỏi danh sách các tàu đang rảnh. Nếu không có, giải pháp của chúng ta sẽ cần thêm một đoàn tàu mới bắt đầu tại ga khởi hành đó. Sau đó, chúng ta tính toán thời điểm đoàn tàu thực hiện chuyến đi này sẽ sẵn sàng tại ga bên kia cho một chuyến đi khác, và thêm đoàn tàu này vào tập hợp các tàu sẵn có tại ga đối diện. Nếu một đoàn tàu rời ga A lúc 12:00 và đến ga B lúc 13:00, với thời gian quay đầu là 5 phút, nó sẽ sẵn sàng cho hành trình ngược lại từ B về A lúc 13:05.

Chúng ta cần có khả năng xác định hiệu quả thời điểm sớm nhất một đoàn tàu có thể rời khỏi một ga; và cập nhật tập hợp các đoàn tàu sẵn có này bằng cách thêm tàu mới hoặc loại bỏ tàu có thời gian sẵn sàng sớm nhất. Điều này có thể được thực hiện bằng cách sử dụng cấu trúc dữ liệu hàng đợi ưu tiên (heap) cho mỗi ga.

Dưới đây là mã Python mẫu giải quyết một bộ test cho bài toán này:

def SolveCase(case_index, case):
  T, (tripsa, tripsb) = case
  trips = []
  for trip in tripsa:
    trips.append([trip[0], trip[1], 0])
  for trip in tripsb:
    trips.append([trip[0], trip[1], 1])

  trips.sort()

  start = [0, 0]
  trains = [[], []]

  for trip in trips:
    d = trip[2]
    if trains[d] and trains[d][0] <= trip[0]:
      # We're using the earliest train available, and
      # we have to delete it from this station's trains.
      heappop(trains[d])
    else:
      # No train was available for the current trip,
      # so we're adding one.
      start[d] += 1
    # We add an available train in the arriving station at the
    # time of arrival plus the turnaround time.
    heappush(trains[1 - d], trip[1] + T)

  print "Case #%d: %d %d" % (case_index, start[0], start[1])

May mắn thay, Python có các phương thức triển khai các thao tác trên cấu trúc dữ liệu heap. Giải pháp này tốn thời gian \(O(n \log n)\), trong đó \(n\) là tổng số chuyến đi, bởi vì tại mỗi chuyến đi, chúng ta thực hiện tối đa một thao tác chèn hoặc một thao tác xóa từ các heap, và các thao tác heap tốn thời gian \(O(\log n)\).

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