ticket_gobble.php

<?php
date_default_timezone_set('Asia/Tokyo');
//$ticketsはarray(目的地,出国日,帰国日);
//出国日と帰国日は1/1からの通算日数(1/1が0になる)
//出国日(昇順) 帰国日(降順) の順でソート済み
$tickets = read_tickets('tickets.txt');
//全然やり方がわからないので手書きで表を作ろうとしましたが
//手書きで
//Aruba     ********
//Kiribati    ***
//Sudan            ***
//Cuba               ********
//Arubaの日程にKiribatiが入ってるからArubaは除外してKiribatiは確定かな・・・
//とやってるとミスしそうだし提出期限に間に合わなそうなのでこの辺をコンピュータにお任せする方針で行くことに

//**********************************************内包する日程探し
//日程が同一と
//他の日程を内包(出国日i <= 出国日j && 出国日j <= 出国日i)するチケットiは削除　
$num = count($tickets);
for($i = 0;$i < $num;$i++){
 //次の項目jの出国日が現在の項目iの入国日と同じになるか過ぎるまでチェック
 for($j=$i+1;$tickets[$i][2] >= $tickets[$j][1]&&!empty($tickets[$j]);$j++){
  //他の日程を内包するチケットiは削除　
  if($tickets[$i][1] <= $tickets[$j][1] && $tickets[$j][2] <= $tickets[$i][2]){
   unset($tickets[$i]);
   break;
  }
 }
} 
$tickets = array_values($tickets);

//**********************************************内包する日程探しここまで
//1/19のようにどのチケットにも含まれない日を探してそこで選ぶチケットを分割すればわかりやすいのでは無いかと考え、どのチケットにも含まれない日を探す事に
//日程が切れる日を探す 旅行中の日をTRUEにする
$list = div_tickets($tickets);

//枚数を数える
//42枚まではプログラムで数えたけど残り20枚は手書きで表を書いて数えました
// http://pic.twitter.com/iEpVT5QVXS
$ans = count_ticket($list);
//dump_tickets($ans,TRUE,FALSE);

//並べ替え
usort($ans,function($a,$b){return($a[0] > $b[0]);});

//回答出力
$num = count($ans);
$ans_txt = "$num ";
foreach($ans as $line){
 $ans_txt.= $line[0]." ";
}
echo $ans_txt."\n";
exit();

function div_tickets($tickets){  
  //1/1からの通算日がキーの配列チケットの日程に含まれている日がTRUE
  $days = array();
  for($i = 0;$i < count($tickets);$i++){
    for($j = $tickets[$i][1];$tickets[$i][2] > $j;$j++)$days[$j] = TRUE;
  }
  //チケットの日程に含まれない期間の初日(日程の切れ目)一覧
  $period = array();
  $flg = TRUE;
  for($i = 0;$i < 365;$i++){
   if($days[$i]){ if(!$flg){$flg = TRUE;$period[] = $i;}
   }else{         if( $flg){$flg = FALSE;} }
  }
  //日程の切れ目でチケットを分ける
  $i=0;$list = array();
  foreach($period as $line){
   for(;$tickets[$i][1] < $line;$i++){
     $list[$line][] = $tickets[$i];
   }
  }
  //$list = 日程の切れ目期間別の配列
  while($i < count($tickets)){
     //echo $tickets[$i][0]." ".$tickets[$i][1]."-".$tickets[$i][2]."\n";
     $list[999][] = $tickets[$i];
     $i++;
  }
 return $list;
}

function count_ticket($list){
//期間の空白で分割したチケットを数える
  foreach($list as $key=>$period){
   //期間内に1つ以下のチケットしか無ければ採用
   //期間内に2つチケットがある場合
   // 1枚目は採用2枚目は1枚目の帰国日と2枚目の入国日がかぶらなければ採用
   if(count($period) <= 2 ){
    $ans[] = $period[0];
    if($period[0][2] < $period[1][1])$ans[] = $period[1];
   }else if(count($period)== 3 || count($period) == 4){
    //期間内のチケットが3枚〜4枚の時
    $last = count($period)-1;
    if($period[0][2] < $period[$last][1]){
     //1枚目の帰国日より最後のチケットの出国日が遅ければ1枚目と最後を採用
     $ans[] = $period[0];$ans[]=$period[$last];
     //本当は3枚の時の2枚目と
     //4枚の時の2枚目と3枚目の採用チェックしないといけないのだけど
     //手作業でチェックしたら該当なしだった…
     // http://pic.twitter.com/iEpVT5QVXS
    }else{
     //どれにも当てはまらなければ1枚目のみ採用
     $ans[] = $period[0];
    }
   }else if(count($period) == 5){
     //期間内5枚の時は1枚目3枚目5枚目が採用(手書き)
     // http://pic.twitter.com/iEpVT5QVXS
    $ans[] = $period[0];
    $ans[] = $period[2];
    $ans[] = $period[4];
   }else{
    //未確定分
    //最終的にはここは未使用になる
    foreach($period as $ticket){
     echo "$key:".$ticket[0]." ".$ticket[1]." ".$ticket[2]."\n";
    }
   }
  }
  return $ans;
}

function read_tickets($filename,$sort = TRUE){
 //ファイルからチケット一覧を読み込んで配列にする
 //日程は1/1からの通算日で管理する
 $file = file($filename);
 $start = array(); $tickets = array(); $days=array(); $period=array();
 foreach($file as $line){
  preg_match('#(^.*?) (.*?)-(.*?)\r$#',$line,$matches);
  $tickets[] = array($matches[1],
                     date('z',strtotime($matches[2])),
                     date('z',strtotime($matches[3])));
  $start[]=date('z',strtotime($matches[2]));
 } 
 //出国日(昇順)と帰国日(降順)でソート
 if($sort){
 foreach($tickets as $key=>$row){ $stt[$key] = $row[1]; $end[$key] = $row[2]; }
 array_multisort($stt,SORT_ASC,$end,SORT_DESC,$tickets);
 }
 return $tickets;
}
function dump_tickets($tickets,$view_z = FALSE,$quit = TRUE){
//確認用
foreach($tickets as $line){ 
   if($view_z){$stt = $line[1];$end = $line[2];}
   else { $stt = date('m/d',strtotime('1/1') + 86400 * $line[1]);
          $end = date('m/d',strtotime('1/1') + 86400 * $line[2]);
   }
   if(strlen($line[0]) < 8 )$country = $line[0]."    ";
   else $country =$line[0];
   echo "$country\t$stt\t$end\n";
  }
  echo count($tickets)."枚\n";
  if($quit)exit();
}