Truck Position Snapshots
MediumStreams · Optiver
A fleet tracker receives GPS reports [truck_id, timestamp, position] (truck_id is a string; timestamp and position are integers). Reports can arrive in any order, so the list events is not sorted by time.
For each time in query_times, build a snapshot of the fleet: for every truck that appears anywhere in events, give [truck_id, position], where position comes from that truck's report with the greatest timestamp <= query_time. If the truck has no report at or before that time, use None. If a truck has several reports with that same greatest timestamp, the one that appears later in events wins.
Each snapshot lists the trucks sorted by truck_id (ordinary string order). Return the snapshots in the same order as query_times.
Example 1
- Input:
- events = [["T2", 5, 40], ["T1", 8, 15], ["T1", 2, 10], ["T2", 1, 30]], query_times = [4, 8]
- Output:
- [[["T1", 10], ["T2", 30]], [["T1", 15], ["T2", 40]]]
- Explanation
- At time 4, T1's latest report is the one at time 2 (position 10) and T2's is at time 1 (30). At time 8, T1's report at 8 counts because the bound is inclusive, and T2's latest is at 5.
Example 2
- Input:
- events = [["b", 3, 7], ["a", 6, 2]], query_times = [3]
- Output:
- [[["a", None], ["b", 7]]]
- Explanation
- Truck
afirst reports at time 6, so at time 3 its position isNone. The snapshot is sorted by id, soacomes first even thoughbappeared first in the input.
Example 3
- Input:
- events = [["x", 4, 1], ["x", 4, 9], ["x", 2, 5]], query_times = [4, 3]
- Output:
- [[["x", 9]], [["x", 5]]]
- Explanation
- Truck
xhas two reports at time 4; the later one in the list (position 9) wins. At time 3 the latest report is the one at time 2.
Constraints
- 0 ≤ events.length ≤ 105
- At most 100 distinct truck ids.
- 0 ≤ query_times.length ≤ 1000
- 0 ≤ timestamp, query_time ≤ 109