PreviousNext
Coding/Searching and sorting

Connected interval clusters

Write codeEasy11 min

Your task

Given an unsorted list of closed integer intervals [start, end], two intervals belong to the same cluster when they overlap or touch at an endpoint, directly, or through a chain of other intervals. Return the number of clusters. Example: [[1,3],[2,4],[7,9],[10,11]] has 3 clusters: {[1,3],[2,4]}, {[7,9]}, and {[10,11]}.

Examples

count_clusters(intervals: list[list[int]]) -> int
Example 1
Inputcount_clusters([[1, 3], [2, 4], [7, 9], [10, 11]])
Output3