Find largest connected group of overlapping intervals
Company: Rubrik
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You are given `n` people, where person `i` works during an inclusive time interval `[start_i, end_i]`.
Define a communication graph:
- Each person is a node.
- Two people have an (undirected) edge if their work intervals **overlap**, i.e.:
\[
\max(start_a, start_b) \le \min(end_a, end_b)
\]
A **work group** is any set of people whose induced subgraph is **connected** (it does not need to be a clique; connectivity through a chain is enough). For example, if A overlaps B and B overlaps C, then `{A,B,C}` is a valid group even if A does not overlap C.
Task: Return the maximum possible size of such a work group (i.e., the size of the largest connected component in this overlap graph).
Constraints (typical interview setting):
- `n` up to `2e5`.
- Times are integers; `start_i <= end_i`.
- Your solution should be around `O(n log n)`.
Quick Answer: This question evaluates understanding of interval overlap modeling, graph connectivity, and algorithmic efficiency by requiring mapping time intervals to an undirected communication graph and identifying its largest connected component.
You are given `n` people, where person `i` works during an inclusive time interval `[start_i, end_i]`.
Build an undirected communication graph: each person is a node, and two people share an edge if their work intervals **overlap**, i.e. `max(start_a, start_b) <= min(end_a, end_b)`.
A **work group** is any set of people whose induced subgraph is **connected** — connectivity through a chain is enough, it does not have to be a clique. For example, if A overlaps B and B overlaps C, then `{A, B, C}` is a valid group even when A and C do not overlap.
Return the maximum possible size of such a work group (the size of the largest connected component in the overlap graph).
The input `intervals` is a list of `[start, end]` pairs. Return `0` for an empty input.
Constraints:
- `n` up to `2e5`.
- Times are integers with `start_i <= end_i` (values may be negative).
- Target an `O(n log n)` solution.
Constraints
- 0 <= n <= 2e5
- start_i <= end_i
- Coordinates are integers and may be negative
- Return 0 when the input is empty
Examples
Input: [[1, 3], [2, 5], [4, 6]]
Expected Output: 3
Explanation: A=[1,3] overlaps B=[2,5], B overlaps C=[4,6]. A and C do not overlap, but the chain connects all three into one group of size 3.
Input: [[1, 2], [5, 6], [10, 11]]
Expected Output: 1
Explanation: No two intervals overlap, so every component has size 1.
Hints
- Two intervals overlap iff max(start_a, start_b) <= min(end_a, end_b). After sorting by start, interval B (which starts no earlier than A) overlaps A exactly when B.start <= A.end.
- Connectivity is transitive, so a connected component's intervals merge into one contiguous range. Sort by start and sweep: keep the largest end seen so far in the current component.
- When the next interval's start exceeds the current component's max end, there is a gap — close the component and start a new one. Track the largest component size as you go.