How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Rubrik.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Rubrik during technical interviews.

Find largest connected group of overlapping intervals

Q: Find largest connected group of overlapping intervals

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.

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.

Input: [[1, 10], [2, 3], [4, 5], [11, 12]]

Expected Output: 3

Explanation: [1,10] overlaps both [2,3] and [4,5], forming one component of size 3. [11,12] is alone (11 > 10).

Input: []

Expected Output: 0

Explanation: Empty input has no people, so the largest group size is 0.

Input: [[5, 5]]

Expected Output: 1

Explanation: A single zero-length interval forms a component of size 1.

Input: [[1, 4], [2, 5], [7, 9], [8, 10], [3, 3]]

Expected Output: 3

Explanation: Sorted: [1,4],[2,5],[3,3] overlap into one component of size 3 (running max end 5). Then [7,9],[8,10] form a separate component of size 2. Largest is 3.

Input: [[1, 100], [2, 2], [50, 50], [99, 99], [200, 300], [250, 260]]

Expected Output: 4

Explanation: [1,100] bridges [2,2],[50,50],[99,99] into a component of size 4. [200,300] overlaps [250,260] for a component of size 2. Largest is 4.

Input: [[0, 0], [0, 0], [0, 0]]

Expected Output: 3

Explanation: Three identical zero-length intervals all overlap each other (max start = min end = 0), forming one group of size 3.

Input: [[-5, -1], [-3, 0], [1, 2]]

Expected Output: 2

Explanation: [-5,-1] overlaps [-3,0] (component size 2). [1,2] starts after 0, so it is separate. Negative coordinates are handled normally.

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.

Quick Overview

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.