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

CodeIQ(チケットゴブル問題)

[CodeIQ]チケットゴブル問題

問題概要

国名と旅行日程が与えられる。
一年間でより多くの国へ行ける旅行プランをたてよ。
入力:国名 旅行期間(例:1/1-1/5)
出力:国名(アルファベット順にソート)

解法

この問題はスケジューリング問題に帰着する。
スケジューリング問題は本問題と本質的に同じ問題である。
方法は、旅行期間が早く終了するものから順に選択することで、
より多くの国へ渡航を可能とするプランを作るというもの。

提出コード(ruby)

require 'date'

COUNTRY = 0
FRONT = 1
BACK = 2

question = []
days = []
t_question =[]
answer = []
count = 0
f = open("tickets.txt"){|file|
	while l = file.gets
		#多次元配列宣言
		t_question[count] = Array.new(3)

		question = l.split(" ")
		days = question[1].split("-")
		# スラッシュで分割
		tmp1 = days[0].split("/")
		tmp2 = days[1].split("/")

		#探索用データ生成1
		t_question[count][COUNTRY] = question[0]
		
		#チケットに必要な日数を算出
		a = Date.new(2016,tmp1[0].to_i,tmp1[1].to_i)
		b = Date.new(2016,tmp2[0].to_i,tmp2[1].to_i)
		period = (b - a).to_i

		#探索用データ生成2
		#日付を整数型へ
		if(tmp1[1].to_i < 10)
			t_question[count][FRONT] = (tmp1[0] + '0' + tmp1[1]).to_i
		else
			t_question[count][FRONT] = (tmp1[0] + tmp1[1]).to_i
		end

		if(tmp2[1].to_i < 10)
			t_question[count][BACK] = (tmp2[0] + '0' + tmp2[1]).to_i
		else
			t_question[count][BACK] = (tmp2[0] + tmp2[1]).to_i
		end

		count = count +1
	end
}

	#終了時間でソート
	t_question = t_question.sort{|a, b|
		a[BACK] <=> b[BACK]
	}

	#探索(すけじゅーりんぐ問題に帰着する)
	tmp = t_question[0][BACK] #ソートしたので最小
	count = 0
	answer[count] = t_question[0][COUNTRY]
	count = 1

	t_question.each_index do |i|
		if t_question[i][FRONT] > tmp
			tmp = t_question[i][BACK]
			answer[count] = t_question[i][COUNTRY]
			count = count + 1
		end
	end

	#回答フォーマット作成
	
	str = count.to_s + ' '
	answer = answer.sort
	answer.each_index do |i|
		str = str + answer[i] + ' '
	end
	p str

解答

問題文は著作上の都合があり、提示できないが、
出力内容は正しいということで、満点をいただいた。