← Lyft Interview InsightsSoftware Engineer
I jumped straight into the standard Meeting Rooms II solution with a single min-heap keyed on end time and the interviewer let me get pretty far before asking how I'd print the assignment history.
Model each job as an interval [start, start+duration) and use a min-heap to track worker availability, but since the tie-breaking rule requires the smallest worker ID among those free at the job's start time, you need to carefully manage the heap to prioritize worker ID when multiple workers are free. After computing the minimum number of workers, simulate the assignment process again to produce the log, ensuring the tie-breaking rule is applied consistently.
Pro tip: Clarify the tie-breaking rule upfront: it's not about who became free earliest, but about the smallest worker ID among all currently free workers. This means you might need to scan or maintain a separate structure to pick the correct worker, which can affect your algorithm's efficiency.
Read the CSV stream line by line, convert each line into a job with start time (in minutes from midnight) and end time (start + duration). Handle potential malformed lines gracefully.
Sort jobs by start time. Use a min-heap of end times to track when workers become free. For each job, if the earliest end time is <= job start, reuse that worker; otherwise, allocate a new worker. The maximum heap size gives the minimum number of workers.
Re-simulate the jobs in start time order. Maintain a set of free worker IDs. When a job starts, first release any workers whose end time <= job start. Then, among free workers, pick the one with the smallest ID. If none free, assign a new worker ID (incrementing counter). Record the assignment.
Print the minimum number of workers and the assignment log, showing each job's start time, duration, and assigned worker ID. Ensure the log is in the order jobs were processed (by start time).
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.