Namaran

Code daily. Without assist.

2026-09-01

events.rs

use std::collections::BTreeSet;

fn events_between(index: &BTreeSet<(u32, u32)>, user: u32, from: u32, to: u32) -> Vec<u32> {
}

index は、利用者 user が時刻 time に操作した記録を (user, time) の組で持つ BTreeSet です。利用者 user の記録のうち、時刻が from 以上 to 以下のものの時刻を、小さい順に Vec にして返す events_between を書いてください。index 全体をたどらず、条件に合う部分だけを読むようにします。該当する記録がなければ空の Vec を返します。from <= to とします。

入力例 1

events_between(&BTreeSet::from([(1, 5), (2, 3), (2, 8), (2, 12), (3, 4)]), 2, 4, 12)

出力例 1

[8, 12]

入力例 2

events_between(&BTreeSet::from([(1, 9), (2, 3), (3, 9)]), 2, 5, 9)

出力例 2

[]

入力例 3

events_between(&BTreeSet::from([(1, 5), (2, 5)]), 1, 5, 5)

出力例 3

[5]
Reference
fn events_between(index: &BTreeSet<(u32, u32)>, user: u32, from: u32, to: u32) -> Vec<u32> {
    index.range((user, from)..=(user, to)).map(|&(_, time)| time).collect()
}

BTreeSet はタプルを辞書式順序(lexicographic order)で並べます。1つ目の要素で比べ、等しいときだけ2つ目で比べるので、user が等しい記録は連続して並び、その中は time の小さい順です。user を固定して time に範囲を付けた (user, from) から (user, to) までは一続きの区間になり、range はその始点を木をたどって探してから、区間の要素だけを順に返します。始点を探す手間は要素数の対数(logarithm)に比例する程度で、全体をたどる必要はありません。

等号で絞る列を先に、範囲で絞る列をあとに置くと、条件に合う記録が1つの区間にまとまります。もし組が (time, user) の順だったら、time の範囲に入る記録をすべて読み、user を1つずつ確かめるしかありません。index.iter().filter(...) で全体をたどっても答えは同じですが、読む量は要素数に比例します。

掲載したのは参考実装で、唯一の正解ではありません。BTreeSet::range は始点が終点より大きいとパニックするので、from > to も受け付けるなら、先に空の Vec を返す分岐を足します。