Task
The following task is a variant of a job scheduling problem.
Example 1:
1 1 2
2 2 3
Day Cost
1 30
2 10
3 20
Possible schedule 1: Job 1 on day 1; Job 2 on day 2. Total cost: 40
Possible schedule 2: Job 1 on day 2; Job 2 on day 3. Total cost: 30
Possible schedule 3: Job 1 on day 1; Job 2 on day 3. Total cost: 50 So, schedule 2 is the best in terms of cost.
Example 2:
1
2
3
4
5 2
1
2
3
2 4
5
3
4
3 1
2
3
4
5 30
10
20
10
40
In this example, it is not possible to schedule all the jobs. This is because jobs 1, 3, 4, and 5 together only have total 3 days available.
Instructions
Input contains 2 + m + n lines.
Line 1: m (the number of jobs)
Line 2: n (the total number of days)
1
Line 2 + m + k for 1 ≤k ≤n: ck (the cost of kth day) Output must contain 2 lines:
Line 1: 0/1 (0 if it is not possible to schedule all the jobs, and 1 otherwise)
Line 2: The minimum possible total cost (if no schedule is possible, this can be an arbitrary number)
• Programming Language: C++. We will compile your code with g++. Make sure that it works.
• Submission: put your code in a file named XXX.cpp where XXX is your roll number. Also, write a short explanation (a paragraph) of what your algorithm does, put this in XXX.pdf. The two files should be uploaded on Moodle (do not zip/compress).
2
