title: Finding the largest interval using Dynamic programming
body: <p><a href="http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf" rel="noreferrer">http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf</a>
  I was doing these questions for practice where I came across one that stumped me.</p>
  
  <blockquote>
    <p>7.(a) Suppose we are given a set L of n line segments in the plane, where each segment has one endpoint on the line y = 0 and one endpoint
    on the line y = 1, and all 2n endpoints are distinct. Describe and
    analyze an algorithm to compute the largest subset of L in which no
    pair of segments intersects.</p>
    
    <p>(b) Suppose we are given a set L of n line segments in the plane,
    where the endpoints of each segment lie on the unit circle x 2 + y 2 =
    1, and all 2n endpoints are distinct. Describe and analyze an
    algorithm to compute the largest subset of L in which no pair of
    segments intersects.</p>
  </blockquote>
  
  <p>I figured out how to do 7a, (the question is a disguised problem to find the largest subset of increasing numbers), in O(n log n) time. Im almost close to giving up on 7b, as I cant figure out a way to do it. </p>
  
  <p>However, is there  a way to convert 7b's premise to something more like 7a's? I feel like that's the right way of approaching the problem, and any help in figuring this out would be much appreciated.</p>