Find smallest partition of intersecting intervals

Question

Given a set of integer intervals SI = {I₁,I₂,...,I_n}, I need to find the smallest partition of SI such that all the intervals of a subset of the partition are intersecting.

That is find the smallest P = {P_i : P_i⊂SI } where P_i∩P_j=∅

and such that ∀I_a,I_b∊P_i, I_a∩I_b≠∅

For example :

Given, SI = {[0,7],[0,6],[1,2],[4,10],[5,10],[9,10]}

The output should be, P*={{[0,7],[0,6],[1,2]},{[4,10],[5,10],[9,10]}} where |P*|=2

What is the name of this problem in literature ? Can anyone hint an efficient optimal algorithm ?

My current solution is a greedy one where I iteratively find the maximum overlapping intervals (using a O(nlogn) time complexity subroutine). For the given example, this outputs a partition P={{[0,7],[0,6],[4,10],[5,10]},{[1,2]},{[9,10]}} of size 3.

enter image description here

Answer 1

1. Find the interval with the smallest endpoint. Some subset must include this interval
2. Make a subset with the selected interval and all the intervals that start before that smallest endpoint. They all intersect with each other, since they all include an interval just before that smallest endpoint. Furthermore, any interval that starts later does not overlap the selected one and can't be included in the same subset.
3. Repeat until you're out of intervals.

Usually, you would begin by sorting the intervals by end point, which makes all of this fast and easy.