Computer Science 320SC – (2019)
Programming Assignment 3
Due: Saturday, September 14th (11:57pm)
Requirements
This assignment requires you to write three efficient algorithms that processes intervals. At least two of them should be implemented via some type of greedy algorithm. It is worth 5% of your total course marks.
All three programs have the same input and output format. The input will begin with an integer n ≤ 1000 denoting how many test cases. This is followed by n lines of an even number 2m of whitespace separated integers:
a1b2a2b2a3b3 …ambm
Each pairs [ai,bi] denotes a closed interval where it is guaranteed that ai ≤ bi for 1 ≤ i ≤ m. The
output will be a single integer per line denoting the answer to the following questions.
Problem 1:
Determine the maximum number of non-overlapping intervals.
Problem 2:
Find the maximum number of intervals that overlap at a single point (on x-axis).
Problem 3:
Compute the largest contiguous interval obtained by taking a union of some of the input intervals.
Sample Input:
4
130234 03121344 0234563624 1112131415
Submission
Output 1 Output 2 Output 3
224 233 336 154
These problem requirements will be worth 2, 2 and 1 marks, respectively, on the computer science automarker https://www.automarker.cs.auckland.ac.nz/. For this assignment you can use any language supported on the automarker and can submit up to 8 times for each problem before occuring a 20% penalty.
1