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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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) .

Find largest connected group of overlapping intervals

Quick Overview

Comments (0)