TopCoder SRM414 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について意訳で説明する。

あなたはレストランのサービス部門のマネージャである。夕方のコースでは、顧客のグループがやってきて、その人たちをテーブルに配置しなければならない。レストランのテーブルは異なった人数の客に対応するために、さまざまなサイズのテーブルを用意している。テーブルへの客の配置は次のような手順で行う。客が現れたとき、まだ客で埋まっていないテーブルの内、そのグループ以上の人数を収められる最小のテーブルを客のために確保する。もし適切なテーブルが複数あれば、その中から任意に一つ割り当てる。もし適切なテーブルが一つもない場合は、顧客は即座に踵を返してその日の夕方は二度と現れない。グループが食事を終え、離れるとき、テーブルは利用できるようになり、新しい顧客を配置することができるようになる。

あなたはこの方法でテーブルに客を割り当てたとき、何人の顧客に逃げられるか知りたい。テーブルのサイズはtable[]という整数型配列で、各要素は収容可能な人数を表す。グループの人数、グループの到着時刻、出発時刻はそれぞれgroupSizes[i]、arrivals[i]、departures[i]である。i番目の要素はすべてグループiに関する情報である。グループは到着時刻順に並べられており、どのグループも同時に来ることはないものとする。もし、あるグループの出発時刻と別のグループの到着時刻が一致した場合は、出発するグループのテーブルは利用可能になっているものとする。逃げられた顧客の総数を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class RestaurantManager {

 public int allocateTables(int[] tables, int[] groupSizes, int[] arrivals, int[] departures) {
  Arrays.sort(tables);
  boolean[] isOccupied = new boolean[tables.length];
  // テーブルにいるグループの出発時刻。
  // i番目の要素がテーブルiを表す。値0はそのテーブルに誰も座ってないことを意味する
  int[] depTime = new int[tables.length];
  int nTurnedAway = 0;
  for( int i=0 ; i<arrivals.length ; i++ ){
   for( int j=0 ; j<tables.length ; j++ ){ // 来た人の時刻により、埋まっていたテーブルを解放
    if( arrivals[i] >= depTime[j] && depTime[j] > 0 ){
     isOccupied[j] = false;
     depTime[j] = 0;
    }
   }
   boolean caught = false;
   for( int j=0 ; j<tables.length ; j++ ){ // 空いているテーブルの探索
    // 最初に見つかったところに顧客を割り当てる(事前にテーブルサイズでソートしておくのがキモ)
    if( isOccupied[j] == false && tables[j] >= groupSizes[i] ){
     isOccupied[j] = true;
     depTime[j] = departures[i];
     caught = true;
     break;
    }
   }
   if( caught == false ){
    nTurnedAway += groupSizes[i];
   }
  }
  return nTurnedAway;
 }

}

得点は201.97/250、1回のsubmitでシステムテストクリア。中央値は約125点。テーブルを小さい順に並び替えておくことで、空いている必要最上限のテーブルサイズを探索するのが容易になります。