Goals: 1. Understanding of the dynamic programming solution to the (one room) we

Question

Goals:

1.     Understanding of the dynamic programming solution to the (one room) weighted interval scheduling problem.

2.     Understanding of the five steps for developing a dynamic programming solution.

Requirements:

1.     Your task is to write a C program to solve the two room weighted interval scheduling problem by using dynamic programming. The first line of the input will be the number of intervals (n) and each of the remaining n lines have three non-negative integers (si, fi, vi) for the start time, finish time, and weight for an interval. The intervals will be ordered by ascending finish time. You should echo the input.

Getting Started:

1.     The input should be read from standard input (which will be one of 1. keyboard typing, 2. a shell redirect (<) from a file, or 3. cut-and-paste). Do NOT prompt for a file name!.

2.     Your solution must use dynamic programming to maximize the total weight of the intervals assigned to the two rooms. The intervals assigned to a room may not overlap (two intervals i and j overlap if either si < sj < fi or si < fj < fi.).

3.     Applying the simple (one room) solution in Notes 7.B to get a maximum solution for one room and then applying again the same technique to the leftover intervals (to assign intervals to the second room) is a non-optimal greedy technique.

4.     n will not exceed 50.

5.     You should print your dynamic programming table(s) with appropriate labeling.

6.     Your solution should be formatted as:

a.     A line with just the number of intervals assigned to the first room.

b.     A line for each of the intervals assigned to the first room: start time, finish time, weight.

c.     A line with just the number of intervals assigned to the second room.

d.     A line for each of the intervals assigned to the second room: start time, finish time, weight.

e.     A line with the total weight that has been achieved

        and appear at the end of your output. No particular ordering of the intervals is required.

Input (a):

9
1 2 1
1 3 3
2 4 1
3 5 1
4 6 2
5 7 1
6 8 2
7 9 1
8 10 2

Output (a):

9
1 2 1
1 3 3
2 4 1
3 5 1
4 6 2
5 7 1
6 8 2
7 9 1
8 10 2
5
1 2 1
2 4 1
4 6 2
6 8 2
8 10 2
4
1 3 3
3 5 1
5 7 1
7 9 1
14

Input (b):

16
10 20 1
15 25 2
10 30 3
20 40 1
15 45 2
30 50 1
40 60 2
25 65 3
50 70 1
35 75 3
60 80 2
15 85 4
70 90 1
35 95 3
80 100 2
72 110 3

Output (b):

16
10 20 1
15 25 2
10 30 3
20 40 1
15 45 2
30 50 1
40 60 2
25 65 3
50 70 1
35 75 3
60 80 2
15 85 4
70 90 1
35 95 3
80 100 2
72 110 3
3
15 25 2
25 65 3
72 110 3
4
10 30 3
40 60 2
60 80 2
80 100 2
17

Input (c):

16
10 20 4
15 25 4
10 30 2
20 40 4
15 45 3
30 50 4
40 60 3
25 65 2
50 70 4
35 75 2
60 80 3
15 85 1
70 90 4
35 95 2
80 100 3
72 110 2

Output (c):

16
10 20 4
15 25 4
10 30 2
20 40 4
15 45 3
30 50 4
40 60 3
25 65 2
50 70 4
35 75 2
60 80 3
15 85 1
70 90 4
35 95 2
80 100 3
72 110 2
5
10 20 4
20 40 4
40 60 3
60 80 3
80 100 3
4
15 25 4
30 50 4
50 70 4
70 90 4
33

Explanation / Answer

#include <stdio.h>

// A job has start time, finish time and profit.
struct Job
{
int start, finish, profit;
};

// A utility function that is used for sorting events
// according to finish time
bool jobComparataor(Job s1, Job s2)
{
return (s1.finish < s2.finish);
}

// Find the latest job (in sorted array) that doesn't
// conflict with the job[i]. If there is no compatible job,
// then it returns -1.
int latestNonConflict(Job arr[], int i)
{
for (int j=i-1; j>=0; j--)
{
if (arr[j].finish <= arr[i-1].start)
return j;
}
return -1;
}

// A recursive function that returns the maximum possible
// profit from given array of jobs. The array of jobs must
// be sorted according to finish time.
int findMaxProfitRec(Job arr[], int n)
{
// Base case
if (n == 1) return arr[n-1].profit;

// Find profit when current job is inclueded
int inclProf = arr[n-1].profit;
int i = latestNonConflict(arr, n);
if (i != -1)
inclProf += findMaxProfitRec(arr, i+1);

// Find profit when current job is excluded
int exclProf = findMaxProfitRec(arr, n-1);

return max(inclProf, exclProf);
}

// The main function that returns the maximum possible
// profit from given array of jobs
int findMaxProfit(Job arr[], int n)
{
// Sort jobs according to finish time
sort(arr, arr+n, jobComparataor);

return findMaxProfitRec(arr, n);
}

// Driver program
int main()
{
Job arr[] = {{3, 10, 20}, {1, 2, 50}};
int n = sizeof(arr)/sizeof(arr[0]);
printf("The optimal profit is %d",findMaxProfit(arr, n));
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.