Chalk Mark Patrol
MediumOnline Assessment
Work out which parked cars a parking officer tickets as she walks a street, timing them with chalk marks.
A street has spaces numbered from 0. Space i belongs to block blocks[i] and allows a stay of limits[i] minutes. The officer's log visits lists her stops in the order she made them (minutes never decrease). Each stop is [minute, space, plate], where plate is the licence plate of the car she found there, or "" if the space was empty.
She keeps a notebook with one entry per plate: the block, the minute its clock started, and the space where she last saw that car. At every stop:
- Empty space: she crosses out the entry whose last-seen space is this one, if there is one. Nothing else happens.
- Occupied space: first she crosses out the entry of any *other* plate last seen in this space (that car has left). Then, if the plate has an entry for this space's block, the car is on its clock: if
minute - start > limits[space]she writes a ticket and restarts that clock atminute. Either way, the entry's last-seen space becomes this space, so a car that shuffles to another space in the same block keeps its clock and is judged by the limit of the space it is in now. If the plate has no entry, or its entry is for a different block, she writes a new entry: this block, startminute, this space.
Input: blocks and limits, equal-length lists of integers; visits, the log.
Output: the tickets, as a list of [minute, space, plate] in the order they were written.
Example 1
- Input:
- [[7,7],[60,120],[[0,0,"CAR1"],[61,0,"CAR1"],[121,0,"CAR1"]]]
- Output:
- [[61,0,"CAR1"]]
- Explanation
- Spaces 0 and 1 are both on block 7. CAR1 is chalked at minute 0 in space 0 (limit 60). At minute 61 it is still there: 61 > 60, so it is ticketed and its clock restarts at 61. At minute 121 the elapsed time is 60, which is not more than 60, so there is no second ticket.
Example 2
- Input:
- [[1,1],[30,40],[[0,0,"CAR1"],[20,0,""],[25,1,"CAR1"],[70,1,"CAR1"],[75,0,"CAR2"]]]
- Output:
- [[70,1,"CAR1"]]
- Explanation
- CAR1 is chalked at minute 0 in space 0. At minute 20 space 0 is empty, so its entry is crossed out. At minute 25 she finds CAR1 in space 1: with no entry it is a fresh car, chalked at 25. At minute 70 it is still there: 70 - 25 = 45 > 40, so it is ticketed. CAR2, chalked at 75 in space 0, is never seen again.
Example 3
- Input:
- [[1,1,2],[30,45,100],[[0,0,"CAR1"],[50,1,"CAR1"],[60,0,"CAR2"],[70,2,"CAR1"],[200,2,"CAR1"]]]
- Output:
- [[50,1,"CAR1"],[200,2,"CAR1"]]
- Explanation
- CAR1 is chalked at minute 0 in space 0. At minute 50 it turns up in space 1 of the same block: its clock carries over, and 50 > 45 (the limit of space 1), so it is ticketed and restarted at 50. At minute 60 CAR2 is in space 0; CAR1's entry now says space 1, so nothing is crossed out. At minute 70 CAR1 appears in space 2, which is a different block, so it gets a fresh entry. At minute 200 it has been there 130 > 100 minutes, so it is ticketed again.
Constraints
- 1 ≤ blocks.length = limits.length ≤ 30; 1 ≤ limits[i] ≤ 240
- 0 ≤ visits.length ≤ 300; minutes are integers between 0 and 100000 that never decrease
- plates are strings of 1 to 8 letters and digits, or the empty string