CODEWITHSUNDEEP
algorithm
Adddison
Adddison

Reputation: 13

Fitting Intervals in two lines

I'm a bit stuck on this problem:

Given a list of n courses, where course i starts at Si and ends at Fi, find an algorithm that fits the courses' schedule in 2 halls where as each hall accommodates only one course at a time.

I thought about solving with the optimal solution for each hall,where you put the minimum Fi each time in the hall then remove all Si that start before the minimum Fi ,Keeping recursively till the courses end.then doing the optimal solution for hall two. found out that optimal solution for each hall does not give the optimal solution for both together.

edit:

An optimal solution is a solution that fits the most courses in the two halls with the minimal time complexity

for example: List of courses:

{(0,1], (0,5], (1,2], (2,3], (4,7], (5,6], (6,8]}

one hall should contain:

{(0,1], (1,2], (2,3], (4,7]}

second one:

{(0,5], (5,6], (6,8]}

However, my algorithm above starts fitting to the first hall; when it gets to 

hall1 = {(0,1], (1,2], (2,3]}
courses = {(0,5], (4,7], (5,6], (6,8]}

the algorithm chooses the earliest end time, adding (5,6]; the optimum solution requires (4,7] to be in hall1, with the other three courses in hall2.

Upvotes: 0

Views: 81

Answers (1)

Prune
Prune

Reputation: 77910

Your attack is good, but too narrow: you need to do that with all halls, filling the one with the earliest available start time, rather than doing one hall entirely before you start the other.

Make a hall_list containing the available (start, end) times of each hall and the sched courses already allocated to that hall.

place_class (hall_list, course_list)
    start = earliest available start time of any hall
    if no such time, return present solution

    hall = the hall with that time
    course_ok = filter course_list for classes where S(i) <= start
    choose i from course_ok with the earliest F(i)

    append i to hall.sched
    remove i from course_list
    hall.start = F(i)

    place_course(hall_list, course_list)

This doesn't work for the example you posted; the same flaw is waiting, but it hits a fragmentation problem first: (1, 2] will be the first course put into hall 2.

Value Refinement:

As above, at every iteration, choose the earliest course with the highest value per hour. A 1-hour class has value 1; the 5-hour class has value 1/5.

Problem:

This also fails; (0,5] is left for last, by which time there's no fit.

Best-fit refinement:

Choose the course with the earliest start time; in case of a tie, choose the earliest end time.

This happens to work for the given case. In fact, if it's known that a solution exists to fit all classes, this will find the solution in linear time. It's even easier if you iterate through courses sorted by start time.

However, if the optimal solution does not place all courses, then this can easily fail. Add two more classes (1,2], (2,3], and this algorithm will fail to see that they should replace (0,5] in hall 2.

DEEPER ATTACK

As @Marcin already pointed out in a deleted answer, this general case is not a simple problem. To guarantee an optimal solution in any case, you need to make a deep search of the placement tree. Write a recursive routine to try all possibilities. Use dynamic programming: memoize your results, so that you don't make redundant calculations. Key on the halls' remaining start times (sorted) and the remaining class list.

There are things you can do in pre-processing that might help real-world examples. For instance, an isolated sequence of short classes can be fused into a common allocation with a higher value. In your given example, you'd fuse (0,1], (1,2], (2,3] into (0,3]. The finish time in (4,7] prevents you from (trivially) doing this with (5, 6], (6, 8].

Does that help move you toward a solution?

Upvotes: 1

Related Questions