Computer Science 320 S2 – (2024)

Programming Assignment 2

Due: August 9th (11:59pm)

Requirements

This assignment requires you to write five efficient algorithms that processes intervals.  At least three of them should be implemented via some type of greedy algorithm. It is worth 5% of your total course marks.

All five programs have the same input and output format. The input will begin with an integer n ≤ 1000 denoting how many testcases. This is followed by n lines of an even number 2m of whitespace separated integers:

a1  b1  a2  b2  a3  b3   . . .  am   bm

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:

Print the sum of the lengths of all intervals.

Problem 2:

Find the smallest gap length between any two non-overlapping intervals.  If no gaps then output the range of the set.

Problem 3:

Determine the maximum number of non-overlapping intervals.

Problem 4:

Find the maximum number of intervals that overlap at a single point (on x-axis).

Problem 5:

Compute the largest contiguous interval obtained by taking a union of some of the input intervals.

Submission

These problem requirements will each be worth 1 marks.  Sumbit diferent solutions to the computer science automarker https://www.automarker.cs.auckland.ac.nz/. For this assignment you need to use the Python programming language and can submit up to 8 times for each problem before occuring a 20% penalty.

Example Input/Output Input:

4

1  3  0  2  3  4

0  3  1  2  1  3  4  4

0  2  3  4  5  6  3  6  2  4

1  1  1  2  1  3  1  4  1  5