Minimum Processes to Drop for Synchronization
Learn this problem
AmazonFULLTIMEOAProblem statement
A team runs n processes. Process i executes during the inclusive interval [starts[i], ends[i]].
A remaining set of processes is synchronized if at least one process in the set has an execution interval that overlaps the execution interval of every other process in the set. Intervals that share an endpoint overlap.
Return the minimum number of processes that must be dropped so that the remaining processes form a synchronized set.
A set containing only one process is synchronized.
Function
minimumProcessesToDrop(starts: int[], ends: int[]) → intExamples
Example 1
starts = [1,2,3,4]ends = [2,3,5,5]return = 1Drop the process with interval [4, 5]. Among the remaining intervals, [2, 3] overlaps [1, 2] at time 2 and [3, 5] at time 3, so the remaining set is synchronized.
Example 2
starts = [1,4,6]ends = [10,5,8]return = 0The interval [1, 10] overlaps both other intervals, so all three processes already form a synchronized set.
Example 3
starts = [1,4,7]ends = [2,5,8]return = 2The three intervals are pairwise disjoint. Keeping any one process produces a synchronized singleton, so two processes must be dropped.