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

• 挑戦者求む！【アルゴリズム】チケットゴブル社の旅行プランを作れ！ by The Essence of Programming 結城 浩│CodeIQ

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

プログラミングコンテストチャレンジブック [第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)