Find largest connected group of overlapping intervals
Problem: Find Largest Connected Group of Overlapping Intervals
You are given n people, where each person i works during an inclusive time interval [start_i, end_i].
We define a communication graph as follows:
- Each person is a node in the graph.
- An undirected edge exists between two people,
aandb, if their work intervals overlap. Two intervals[start_a, end_a]and[start_b, end_b]overlap ifmax(start_a, start_b) <= min(end_a, end_b).
A work group is defined as any set of people whose induced subgraph is connected. It is important to note that this does not require the subgraph to be a clique; connectivity through a chain of overlaps is sufficient. For example, if person A overlaps with person B, and person B overlaps with person C, then {A, B, C} forms a valid work group, even if person A does not directly overlap with person C.
Task: Return the maximum possible size of such a work group. This is equivalent to finding the size of the largest connected component in the defined overlap graph.
Constraints:
ncan be up to2e5(200,000).- All times (
start_i,end_i) are integers. - For all intervals,
start_i <= end_i. - Your solution should achieve a time complexity of approximately
O(n log n).
AI interview prep
Core dilemma
The central engineering conflict is efficiently constructing and traversing an implicitly defined overlap graph to find the largest connected component, all while adhering to a strict O(N log N) time complexity constraint that rules out naive O(N^2) pairwise interval comparisons.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Find largest connected group of overlapping intervals
Problem: Find Largest Connected Group of Overlapping Intervals
You are given n people, where each person i works during an inclusive time interval [start_i, end_i].
We define a communication graph as follows:
- Each person is a node in the graph.
- An undirected edge exists between two people,
aandb, if their work intervals overlap. Two intervals[start_a, end_a]and[start_b, end_b]overlap ifmax(start_a, start_b) <= min(end_a, end_b).
A work group is defined as any set of people whose induced subgraph is connected. It is important to note that this does not require the subgraph to be a clique; connectivity through a chain of overlaps is sufficient. For example, if person A overlaps with person B, and person B overlaps with person C, then {A, B, C} forms a valid work group, even if person A does not directly overlap with person C.
Task: Return the maximum possible size of such a work group. This is equivalent to finding the size of the largest connected component in the defined overlap graph.
Constraints:
ncan be up to2e5(200,000).- All times (
start_i,end_i) are integers. - For all intervals,
start_i <= end_i. - Your solution should achieve a time complexity of approximately
O(n log n).