こんにちは。SRE / バックエンドエンジニアのマノメです。

前回の記事を読んで、以前私が思いつきで作った、「全員で会議できる時間はいつか？」を調べるコードを書いたことを思い出しました。
どういうものかというと、チームメンバーの数日間の出勤記録をもとに全員が揃っている時間を割り出す、という至ってシンプルなものです。

弊社では現在、コアタイムなしのフレックスタイム制で、多くのメンバーがフルリモート出勤です。
会議をしたい！となったらもちろん、開始時間を決めてその時間に出勤するようにするべきなのですが、とはいえ生活時間を急に変えるというのは朝が弱い私のような人間にとってはなかなか大変です。
なので、チームメンバーが全員揃う時間帯を割り出して会議を設置すれば、そういった杞憂をせず済むと考えたわけです。
特にチームの再編を行った際は、このデータが参考になるのではないでしょうか。
そういった私の思いつきでコードを書いたものの、そのときにはすでにチームができて数ヶ月経って会議時間も決まっていたため、誰にも披露することなくお蔵入りになりました。

今回は、このとき作ったコードを元に、累積和のアルゴリズムのことをちょっとだけ話そうと思います。

作ったもの

Go で書いています。
余談ですが、くらしのマーケットでは一部で Go が使われている箇所があります。

用意したデータ

A 〜 D の 4 人の出勤記録をテキストに書き起こします。
※記事のために適当な値を作っています

# A
08:54-17:24
09:42-17:37
09:39-18:24
10:46-19:33
# B
10:23-20:32
10:16-18:28
10:28-19:42
10:45-19:36
# C
10:08-18:32
10:07-19:48
10:00-19:49
10:11-19:27
# D
11:14-21:00
11:02-20:47
11:47-21:19
10:59-21:04

書いたコード

func main() {
    // データを読み込んでいい感じにする
    // [[As_start_time, As_end_time], [Bs_start_time, Bs_end_time], ...]
    input := read()

    data := make([]int, 60*24)
    for _, i := range input {
        // i[0] が 出勤時間, i[1] が 退勤時間
        data[i[0]] += 1
        data[i[1]] -= 1
    }

    // 必ず全員いる時間 = データの数
    max := len(input)

    // 全員いる時間を探す
    cur := 0
    isMax := false
    start, end := 0, 0
    for index, d := range data {
        cur += d
        // 全員が揃った時間の記録
        if !isMax && cur == max {
            start = index
            isMax = true
        }
        // 全員が揃っていた最後の時間の記録
        if isMax && cur == max-1 {
            end = index - 1
            isMax = false
        }
    }

    fmt.Printf("%d:%d - %d:%d\n", start/60, start%60, end/60, end%60)
}

結果

与えられたデータより、11:47 - 17:23 が適切な会議の設定時間となります。

解説

さて、アルゴリズムについての話ですが、今回使ったのはいもす法という素晴らしいアルゴリズムです。
これは、累積和を用いて複数の要素の重なりや深さなどを計算するものです。

例えば以下のような出勤表があるとします。

f:id:curama-tech:20210122132636p:plain — 出勤時間のグラフ

これをもとに、愚直に累積和のデータを作るならこうなるでしょう。

	09:00	10:00	11:00	17:00	18:00	19:00
A	0	1	1	1	1	1
B	1	1	1	1	0	0
C	0	0	1	1	1	0
合計	1	2	3	3	2	1

この「合計」の配列を用意して計算することになります。
ただ、プロットするのに以下のような処理が必要です。

input := read()
data := make([]int, 60*24)

// データのプロット
for _, i := range input {
    // i[0] が 出勤時間, i[1] が 退勤時間
    // 1 つのデータに対して、該当範囲を"塗りつぶす"イメージ
    for k := i[0]; k < i[1]; k++ {
        data[k]++
    }
}

max := len(input)

// シミュレート
start, end := 0, 0
isMax := false
for index, d := range data {
    // 全員が揃った時間の記録
    if !isMax && d == max {
        start = index
        isMax = true
    }
    // 全員が揃っていた最後の時間の記録
    if isMax && d == max-1 {
        end = index - 1
        isMax = false
    }
}

これは、人数(N) と時間範囲(T) に対して、データのプロットに必要な計算量は O(N*T) 、シミュレートに必要な計算量は O(T) となり、合計で O(N*T + T) となります。

さて、いもす法を用いると、かなりシンプルに、計算量も抑えられます。
データの作り方が肝で、「出勤したら+1、退勤したら-1 する」という方法を取ります。

	09:00	10:00	11:00	19:00	20:00
A	0	+1	0	0	-1
B	+1	0	0	-1	0
C	0	0	+1	-1	0

よって、データのプロットは最初に書いたコードの通り、

for _, i := range input {
    // i[0] が 出勤時間, i[1] が 退勤時間
    data[i[0]] += 1
    data[i[1]] -= 1
}

となります。
この場合、データのプロットに必要な計算量は O(N) 、シミュレートに必要な計算量は O(T) となり、合計で O(N+T) となります。
処理がシンプルになり、計算量もかなり減ります。

これなら、人数が大幅に増えても計算量が大きくなりすぎないですね。

さいごに

結局、いもす法を使って作った「全員で会議できる時間を探す」というコード自体は、実用性があるのかないのかよくわからない結果になりましたが、いもす法は実際のデータ分析においてとても役に立つと思います。
例えばこのご時世ですから、部屋の中に一定以上の人数がいる時間帯を調べて換気の強さを調整するというのができそうですね。
くらしのマーケットでいうなら、登録している出店者のサービス提供が最も盛んな時間帯を調べたい、といった場面で役に立つかもしれません。

こういったアルゴリズムは知っているとひょんなことで役に立つかもしれないので、そういった知識を深める場として競技プログラミングはいい機会だと思います。
競技に参加しなくても、エクササイズとして過去問に取り組むだけで勉強になると思います。
ぜひ、挑戦してみてください！