チケットゴブル問題の参照ファイルです。

answer.txt

62 Afghanistan Angola Antarctica Austria Azerbaijan Barbados Belarus Botswana Burundi Canada China Cyprus Denmark Ecuador Eritrea Ethiopia Finland Georgia Germany Ghana Greece Guadeloupe Jordan Kiribati Liberia Libya Liechtenstein Macao Malawi Malaysia Martinique Mongolia Montenegro Montserrat Myanmar Namibia Narnia Niger Nigeria Oman Palau Poland Portugal Romania Rwanda Samoa Senegal Serbia Seychelles Slovakia Slovenia Somalia Sudan Sweden Switzerland Tajikistan Tokelau Turkey Uganda Ukraine Zambia Zimbabwe

five.txt

Austria 1/1-1/5
Belgium 1/6-1/10
Canada 1/7-1/8
Denmark 1/9-1/10
Egypt 1/18-1/30

solve.rb

#! /usr/bin/ruby

class Ticket
  def initialize(country, from_month, from_day, to_month, to_day)
    if from_month > to_month
      abort("Invalid request: from_month == #{from_month} > to_month == #{to_month}")
    elsif from_month == to_month and from_day >= to_day
      abort
    end
    @country, @range = country, Range.new(from_month * 100 + from_day, to_month * 100 + to_day)
  end
  def first
    @range.first
  end
  def last
    @range.last
  end
  def include?(e)
    @range.include?(e)
  end
  def size
    @range.size
  end
  def conflict?(r)
    self.include?(r.first) || self.include?(r.last) || r.include?(self.first) || r.include?(self.last)
  end
  def to_s
    @country + '(' + @range.to_s + ')'
  end
  attr_reader :country
end

class Solver
  def initialize(filename)
    @requests = []
    File::open(filename) do |f|
      while line = f.gets
        line.chomp!
        if line.match(/^(\S+)\s+(\d+)\/(\d+)-(\d+)\/(\d+)/)
          country, from_month, from_day, to_month, to_day = $1, $2.to_i, $3.to_i, $4.to_i, $5.to_i
          @requests << Ticket.new(country, from_month, from_day, to_month, to_day)
        else
          abort("ERROR:#{line}")
        end
      end
    end
  end

  # 終了日の早いものから順に選ぶ（最善）
  def solve1
    rs = @requests.sort { |a, b| a.last <=> b.last }
    result = []
    while !rs.empty?
      r = rs.shift
      rs.delete_if { |e| e.conflict?(r) }
      result << r
    end
    result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
  end

  # 開始日が早いものから順に選ぶ
  def solve2
    rs = @requests.sort { |a, b| a.first <=> b.first }
    result = []
    while !rs.empty?
      r = rs.shift
      rs.delete_if { |e| e.conflict?(r) }
      result << r
    end
    result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
  end

  # 期間が短いものから順に選ぶ
  def solve3
    rs = @requests.sort { |a, b| a.size <=> b.size }
    result = []
    while !rs.empty?
      r = rs.shift
      rs.delete_if { |e| e.conflict?(r) }
      result << r
    end
    result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
  end

  # できるだけ重なりの少ないものから順に選ぶ
  def solve4
    conflict_count = Hash.new(0)
    @requests.each do |r|
      rs = @requests.clone
      conflict_count[r.country] = rs.keep_if { |s| r.conflict?(s) }.size
    end
    rs = @requests.sort { |a, b| conflict_count[a.country] <=> conflict_count[b.country] }
    result = []
    while !rs.empty?
      r = rs.shift
      rs.delete_if { |e| e.conflict?(r) }
      result << r
    end
    result.size.to_s + ' ' + result.map {|r| r.country }.sort.join(' ')
  end
end

# puts Solver.new("tickets.txt").solve1
# puts Solver.new("tickets.txt").solve2
# puts Solver.new("tickets.txt").solve3
# puts Solver.new("tickets.txt").solve4
puts
puts "answer for five.txt:"
puts Solver.new("five.txt").solve1
puts
puts "answer for tickets.txt"
puts Solver.new("tickets.txt").solve1

tickets.txt

Afghanistan 4/17-4/18
Albania 9/25-10/2
Algeria 11/23-11/25
Andorra 8/22-8/27
Angola 5/18-5/19
Anguilla 3/2-3/3
Antarctica 6/3-6/5
Argentina 2/2-2/7
Armenia 5/18-5/21
Aruba 1/1-1/8
Australia 3/25-3/31
Austria 2/7-2/8
Azerbaijan 4/11-4/13
Bahamas 8/20-8/24
Bahrain 7/26-7/31
Bangladesh 6/22-6/26
Barbados 9/5-9/7
Belarus 9/8-9/15
Belgium 6/8-6/10
Belize 7/6-7/10
Benin 8/6-8/10
Bermuda 9/3-9/6
Bhutan 9/14-9/19
Botswana 11/23-11/24
Brazil 7/10-7/13
Bulgaria 2/15-2/22
Burundi 3/6-3/8
Cambodia 3/16-3/22
Cameroon 12/3-12/9
Canada 9/26-9/27
Chad 12/1-12/3
Chile 5/7-5/13
China 1/14-1/18
Colombia 3/2-3/5
Comoros 8/26-8/28
Congo 4/2-4/9
Cuba 1/10-1/17
Cyprus 6/27-6/28
Denmark 2/22-2/24
Djibouti 5/19-5/24
Dominica 12/19-12/24
Ecuador 12/7-12/8
Egypt 12/5-12/6
Eritrea 10/15-10/17
Estonia 11/4-11/11
Ethiopia 8/1-8/6
Fiji 11/19-11/20
Finland 2/18-2/19
France 6/29-7/3
Gabon 3/27-4/3
Gambia 9/25-9/28
Georgia 2/29-3/2
Germany 3/17-3/21
Ghana 11/7-11/9
Gibraltar 7/10-7/15
Greece 11/27-11/28
Greenland 5/3-5/6
Grenada 10/11-10/18
Guadeloupe 12/20-12/24
Guam 4/11-4/16
Guatemala 3/6-3/9
Guernsey 9/13-9/16
Guinea 6/4-6/8
Guyana 10/26-10/30
Haiti 1/20-1/24
Hungary 1/20-1/24
Iceland 7/25-8/1
India 7/21-7/28
Indonesia 8/20-8/27
Iraq 9/12-9/18
Ireland 10/25-10/28
Israel 6/11-6/18
Italy 2/6-2/12
Jamaica 1/23-1/25
Jersey 1/31-2/6
Jordan 12/5-12/6
Kazakhstan 4/2-4/8
Kenya 7/29-8/4
Kiribati 1/3-1/5
Kuwait 7/14-7/18
Kyrgyzstan 6/13-6/14
Latvia 2/6-2/12
Lebanon 1/10-1/14
Lesotho 1/29-2/3
Liberia 7/14-7/18
Libya 4/19-4/21
Liechtenstein 3/30-4/2
Lithuania 5/2-5/8
Luxembourg 8/28-8/31
Macao 4/3-4/10
Madagascar 11/15-11/22
Malawi 9/20-9/21
Malaysia 11/10-11/16
Maldives 10/31-11/5
Mali 9/17-9/24
Malta 8/23-8/25
Martinique 7/28-7/29
Mauritania 10/13-10/20
Mauritius 12/21-12/28
Mayotte 10/24-10/29
Mexico 2/24-3/2
Monaco 12/4-12/7
Mongolia 5/6-5/8
Montenegro 8/9-8/11
Montserrat 12/12-12/16
Morocco 6/26-6/29
Mozambique 2/18-2/21
Myanmar 11/29-12/3
Namibia 10/10-10/12
Narnia 6/8-6/9
Nauru 12/15-12/19
Nepal 5/6-5/8
Netherlands 12/8-12/12
Nicaragua 9/29-10/2
Niger 4/28-5/5
Nigeria 7/23-7/25
Niue 5/14-5/21
Norway 5/8-5/9
Oman 2/13-2/16
Pakistan 6/11-6/16
Palau 6/11-6/14
Panama 7/18-7/20
Paraguay 11/9-11/15
Peru 12/5-12/7
Philippines 4/6-4/11
Pitcairn 6/24-6/29
Poland 8/27-8/28
Portugal 5/27-5/31
Qatar 1/16-1/23
Romania 7/5-7/7
Rwanda 6/6-6/7
Samoa 7/1-7/2
Senegal 11/19-11/20
Serbia 6/20-6/24
Seychelles 8/12-8/17
Singapore 7/23-7/25
Slovakia 6/16-6/17
Slovenia 9/17-9/19
Somalia 10/22-10/27
Spain 9/24-9/29
Sudan 1/8-1/10
Suriname 11/28-11/29
Swaziland 6/10-6/16
Sweden 8/23-8/24
Switzerland 8/31-9/4
Tajikistan 1/20-1/23
Thailand 6/27-6/30
Togo 11/16-11/17
Tokelau 3/28-3/29
Tonga 5/8-5/10
Tunisia 11/16-11/23
Turkey 7/11-7/12
Turkmenistan 11/28-11/30
Tuvalu 3/15-3/22
Uganda 10/6-10/9
Ukraine 9/28-9/29
Uruguay 7/1-7/6
Uzbekistan 2/26-3/4
Vanuatu 8/15-8/21
Yemen 6/24-6/29
Zambia 1/27-2/3
Zimbabwe 10/29-11/5