読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

CodeIQ《結城浩のチケットゴブル問題》に挑戦した(Python)

「この問題蟻本でみたことある!」って感じだった

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

概要

出発日時と到着日時があるチケットがいくつか与えられる。
できるだけ多くのチケットを使用するためにはどのチケットを使えばいいか

解法

いわゆる区間スケジューリング問題なので、到着日時が早い順にチケットを使っていけばいい
ちなみにチケットの価値に差がある場合には動的計画法を使えばよいはず

使ったソースコード

import sys

ticket = []
for line in sys.stdin:
    country, date = line.strip().split(' ')
    start_str, end_str = date.split('-')
    temp_start = start_str.split('/')
    start = int(temp_start[0])*100 + int(temp_start[1])
    temp_end = end_str.split('/')
    end = int(temp_end[0])*100 + int(temp_end[1])
    ticket.append((end, start, country))

ticket.sort()
last = 0

result = []
for end, start, country in ticket:
    if start > last:
        last = end
        result.append(country)

result.sort()
print len(result), ' '.join(result)
-->