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(starta,startb)≤min(enda,endb)
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)
.