TopCoder SRM438 Div2 250Pts

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

luckySetという整数の集合が与えられる。luckySetに属する2つの要素でAがBより大きく、AとBが共に正の整数である区間[A, B]は、もしAとBの間の整数がなければ不幸であると考えられる。luckySetという整数型配列と、nというluckySetの最大値を超えないような整数が与えられたとき、nを含む不幸な区間の数を返すメソッドを作成せよ。

例えば、luckySet={1, 7, 14, 10}、n=2である場合、1と7の間に2があり、2～6の整数を用いて、2を含むような区間を考えてみると、[2, 6]、[2, 5]、[2, 4]、[2, 3]の4つが該当する。

私の解答はこちら。

import java.util.Arrays;

public class UnluckyNumbers {

 public int getCount(int[] luckySet, int n) {
  for( int i=0 ; i<luckySet.length ; i++ ){
   if( luckySet[i] == n ) return 0; // Setの値があったら区間は作れないので0
  }
  Arrays.sort(luckySet); // ソートして、

  int[] between = new int[2]; // どこの間の区間にnがあるか検討する
  for( int i=1 ; i<luckySet.length ; i++ ){
   if( luckySet[i] > n ){
    between[0] = luckySet[i-1] + 1;
    between[1] = luckySet[i] - 1;
    break;
   }
  }
  if( n < luckySet[0] ){ // nがluckySetの最小値よりも小さい場合
   between[0] = 1;
   between[1] = luckySet[0] - 1;
  }
  int nInterval = 0; // 以下で区間の数を数える
  for( int i=between[0] ; i<=between[1] ; i++ ){
   if( i < n ){
    nInterval += between[1] - n + 1;
   }else if( i == n){
    nInterval += between[1] - n;
   }
  }
  return nInterval;
 }

}

得点は153.40/250、2回目のsubmitでシステムテストクリア。1回目の提出では、nがluckySetの最小値を下回る場合の処理を間違えていた。