TCHS09 Elimination Round 2 Hard

問題

ミーティングの時間に遅れたり早く来たりするんだけど、全てのミーティングを同じ時間だけずらして待ち時間が最低になるようなずらしかたが何通りありますか。

解

全ての時間を同じだけずらすので、会議の待ち時間順で考えて真ん中にあるぶんだけずらすといい。

n時間早くくるのを -n、遅くくるのを n として、たとえば会議の待ち時間を順番に並べたら

 -7, -2, 3, 6, 8

となったとき、真ん中にある3だけ、つまり3時間だけ遅らせれば待ち時間は最低になる。

会議の個数が奇数だと、真ん中を選ぶだけなので一通りだなんだけど、偶数の場合は真ん中二つの間にある数の個数通りある。たとえば、

 -5, -3, 1, 9

とすると、-3と1の間にある数の個数、つまり -3, -2, -1, 0, 1 の5通りで待ち時間は最低になる。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class WizardsAppointments {
    public int scheduleAdjustment(int[] scheduledTimes, int[] arrivalTimes) {
        int[] p = new int[scheduledTimes.Length];
        if((scheduledTimes.Length % 2) == 1)
            return 1;

        for (int i = 0; i < scheduledTimes.Length; ++i)
            p[i] = scheduledTimes[i] - arrivalTimes[i];
        Array.Sort(p);

        return p[scheduledTimes.Length / 2] - p[scheduledTimes.Length / 2 - 1] + 1;
    }
}