Scheduling Problem?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Scheduling Problem?

Post by Hackson »

Suppose we have N sets of integers.
Each set of integers is represented by [A, B], a closed interval of integers such that A <= B.
Find the minimum number of sets such that those sets can cover [L, H], where 0<=L<=H<=2000, note that the selected sets can be overlapped.

Is it a DP problem? I can't figure it out.. :oops:
Solving problem is a no easy task...
misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

One of the intervals has to contain the point 2000. Try all possibilities. Each time you have to find an optimal cover for [0, beginning of the chosen interval].
Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by Hackson »

misof wrote:One of the intervals has to contain the point 2000. Try all possibilities. Each time you have to find an optimal cover for [0, beginning of the chosen interval].
Thanks for your idea. But what if [a, b] such that a >= b?
e.g. [1999, 5] would contain {1999, 2000, 0, 1, 2, 3, 4, 5}
under a cycling set, would the technique be different from yours??
Solving problem is a no easy task...
Post Reply

Return to “Algorithms”