I solved this problem with gready algo and get AC (thanks weak tests). So my program failed on this test:
6
1 5
2 6
3 7
4 8
5 9
6 10
My AC prog gives
1
5 9
But of cause it is wrong! And correct answer is 2 segments. I think some new test should be added. GOOD LUCK!

Your test is added, but you are the only author who lost AC. :) By the way, we believe that tests in this problem are weak. If you have more tests you can send them to acm_support@acm.timus.ru .

Now I returned my AC! )) Just another gready algo. Anyway, thanks for the adding!