Solution is from here:
http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf
Some explanation:
Step 1: Find-Intersection
This step is to find a region [a,b] that does not have intersection with other regions [$a_i$,$b_i$]. So this is a minimal regions.
Step 2: Partition-Right and Partition-Left-Middle
Step 3: sort left part and right part.
Some wrong solution before:
get a pivot region arbitrary. and then divide the whole array as 3 parts: left, middle, right.
left part is bi less than middle and right part is ai greater than middle. middle part is the set of regions that have intersection with the given pivot region.
The problem here is that: middle region may have two regions that are disjoint. therefore, the two regions still need sort, thus violating the fact that middle part does not require sorting. For example, the pivot regions is [5, 9] and middle part is [6,7], [8,9] and [5,9]. then [6,7] and [8,9] definitely need sort.
