title: Connected components in union of segments
body: <p>I have N segments (1 ≤ N ≤ 10^5) on a 1D number line. Each segment contains all reals x such that starting point ≤ x ≤ ending point.</p>
  
  <p>We can say that the "union" of a set of segments is the set of all x that are contained within at least one segment. The "complexity" of a set of segments is the number of connected regions represented in its union.</p>
  
  <p>Over all 2^n subsets of the segments, we want to compute the sum of the complexities.</p>
  
  <p>Example:</p>
  
  <p>You have three segments, [1, 6], [2, 3], [4, 5] where in [a, b] a = starting point, b = ending point.</p>
  
  <p>The solution is 8. Here are the complexities of each subset:
  [1,6]⟹1,[2,3]⟹1,[4,5]⟹1</p>
  
  <p>{[1,6],[2,3]}⟹1,{[1,6],[4,5]}⟹1,{[2,3],[4,5]}⟹2</p>
  
  <p>{[1,6],[2,3],[4,5]}⟹1</p>
  
  <p>The answer is 1+1+1+1+1+2+1=8.</p>
  
  <p>Clearly we cannot iterate over all subsets (2^N subsets!) Could anyone give me a hint or push me in the right direction?</p>