Yup, that is pretty much the solution I discussed with the interviewer after writing the code above. We ran out of time to write out the full code, but hopefully coming up with the rough description of a solution like yours was satisfactory.

Waiting with bated breath for the interview feedback... :-)