Peaceful Sample Intervals
Preview mode. Log in to edit, run, submit, and save progress.
Peaceful Sample Intervals
A laboratory keeps n bacterial samples arranged in a straight row, labeled from 1 to n. The lab also has m toxic interaction records. Each record is given by two lists: vulnerable[i] is the bacterium that gets harmed, and toxic[i] is the bacterium that causes the harm. For counting safe segments, the direction of harm does not change the condition: if a chosen continuous interval contains both bacteria from any toxic record, that interval is considered unsafe. Your task is to count how many continuous intervals of samples are peaceful, meaning they do not contain both endpoints of any toxic interaction record.
Examples
5 2 2 3 5 4
9
Explanation: There are 5 samples and 2 toxic records: (2, 5) and (3, 4). Any interval containing both 2 and 5 is unsafe, and any interval containing both 3 and 4 is also unsafe. After excluding all such intervals, 9 peaceful intervals remain.
Approach hint
For a toxic pair (a, b), any interval containing both min(a,b) and max(a,b) is unsafe.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.