The interview included multiple algorithm questions in the same category:
-
Minimum concurrent resources for intervals
You are given a list of time intervals, where each interval represents a meeting or a CPU task with a start time and an end time. Return the minimum number of rooms or CPU slots required so that all intervals can run without overlap conflicts.
Example: if intervals are
[0, 30]
,
[5, 10]
, and
[15, 20]
, the answer is
2
because at most two intervals overlap at the same time.
-
Equivalent CPU-capacity variant
Solve the same problem again, but framed as finding the minimum number of CPUs needed to run all jobs whose active windows are given as intervals.
-
One-dimensional collision simulation
You are given an array of integers representing moving objects on a line. A positive value moves to the right, and a negative value moves to the left. When two objects moving toward each other collide, the one with smaller absolute value disappears. If they have equal absolute value, both disappear. Return the final state after all collisions are resolved.
The interview version was described as a simplified variant of the standard stack-based collision simulation problem.
Implement efficient solutions and discuss the time and space complexity.