Katkat
Back

Find largest connected group of overlapping intervals

RubrikSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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

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