Covering segments by points

Question

I did search and looked at these below links but it didn't help .

1. Point covering problem
2. Segments poked (covered) with points - any tricky test cases?
3. Need effective greedy for covering a line segment

Problem Description:

 You are given a set of segments on a line and your goal is to mark as
 few points on a line as possible so that each segment contains at least
 one marked point

Task.

  Given a set of n segments {[a0,b0],[a1,b1]....[an-1,bn-1]} with integer
  coordinates on a line, find the minimum number 'm' of points such that 
  each segment contains at least one point .That is,  find a set of 
  integers X of the minimum size such that for any segment [ai,bi] there 
  is a point x belongs X such that ai <= x <= bi

Output Description:

  Output the minimum number m of points on the first line and the integer 
coordinates of m points (separated by spaces) on the second line

Sample Input - I

3
1 3
2 5
3 6

Output - I

1  
3

Sample Input - II

4
4 7
1 3
2 5
5 6

Output - II

2   
3 6 

I didn't understand the question itself. I need the explanation, on how to solve this above problem, but i don't want the code. Examples would be greatly helpful

Answer 1

Maybe this formulation of the problem will be easier to understand. You have n people who can each tolerate a different range of temperatures [ai, bi]. You want to find the minimum number of rooms to make them all happy, i.e. you can set each room to a certain temperature so that each person can find a room within his/her temperature range.

As for how to solve the problem, you said you didn't want code, so I'll just roughly describe an approach. Think about the coldest room you have. If making it one degree warmer won't cause anyone to no longer be able to tolerate that room, you might as well make the increase, since that can only allow more people to use that room. So the first temperature you should set is the warmest one that the most cold-loving person can still tolerate. In other words, it should be the smallest of the bi. Now this room will satisfy some subset of your people, so you can remove them from consideration. Then repeat the process on the remaining people.

Now, to implement this efficiently, you might not want to literally do what I said above. I suggest sorting the people according to bi first, and for the ith person, try to use an existing room to satisfy them. If you can't, try to create a new one with the highest temperature possible to satisfy them, which is bi.