Interview Questions/Coding/Peaceful Sample Intervals

Peaceful Sample Intervals

Preview mode. Log in to edit, run, submit, and save progress.

Medium

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

Example 1
Input:
5
2
2 3
5 4
Output:
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.

solution.cpp