title: Complement of a set of intervals
body: <p>I have a set of intervals inside the range [0,k].</p>
  <p>How can I produce the complement set of this set of intervals?</p>
  <p>I can come up with an algorithm, but it requires sorting the intervals.</p>
  <p>Therefore, the complexity is O(nlogn), where n is the number of intervals.</p>
  <p>Is there any faster algorithm to do this? If not, is there any way to prove that this is the optimal complexity?</p>
  <p>Thank you.</p>