CS 503 - Advanced Programming I Programming Assignment 2

Programming Assignment 2 - Interval Partitions

Advanced Programming I, Spring 2007

Due Date

This assignment is due by 5:30 p.m. on Tuesday, 13 February.

See the assignment turn-in page (last modified on 14 January 2006) for instructions on turning in your assignment.

Background

An interval is a pair of integers (a, b) with a ≤ b; a and b are the interval endpoints. Two intervals (a1, b1) and (a2, b2) overlap if a1 ≤ a2 ≤ b1 or a1 ≤ b2 ≤ b1 or both.

Given a set S of intervals, an interval partition of S is a set of subsets { S1, S2, …, Sn } with the properties

  1. every interval in S appears in exactly one subset, and

  2. no pair of intervals in the same subset overlap.
An interval partition with n subsets has size n.

Given a set S of n intervals, one simple way to form an interval partition of S is to put each interval in its own subset; the resulting partition has size n. Generally, however, it is better to have a partition's size be as small as possible.

Greedy scan is another way of creating interval partitions. Given an interval set S, greedy scan considers each interval in S (the scan) and puts every interval that fits in a subset (greedy): 

greedy scan(S)
  create an empty partition P
  while S isn't empty
    create an empty subset S'
    for each interval i in S
      if i does not overlap any interval in S'
	remove i from S
	add i to S'
    add S' to P
  return P

The Problem

Write a program that reads an interval set from std-in and writes two interval partitions to std-out. Both interval sets are created using the same greedy-scan algorithm, which you create. The first partition comes from applying the greedy-scan algorithm to the interval set as read from std-in. The second partition comes from applying the greedy-scan algorithm to the interval set after the intervals have been re-ordered (that is, sorted) to provide better results; it is up to you to figure out how the intervals should be re-ordered.

Input

Input is a sequence of integers; consecutive pairs of integers are the endpoints for an interval. Adjacent integers are separated by at least one space character.

If the input is incorrect, your program should print an informative error message preceded by "! " (that's bang-space) to std-err and exit with no further processing.

Output

Output is two interval partitions; the partitions are separated by at least one blank line (a line containing zero or more space characters ending with a newline). Each subset in a partition is printed on one line; the intervals in a partition may appear in any order, but the interval endpoints must be ordered properly.

Testing

My solution partition-intervals is available in the class assignment directory /export/home/class/cs-503/a2. Remember the purpose of this assignment is to implement a correct solution, not to copy the behavior of my solution. If my solution's wrong and you copy the incorrect behavior, you're going to lose points.

You can use gen-intervals, also available in the class assignment directory, to generate intervals. When run, it writes an randomly generated interval set to std-out. You can use it with your program like so: 

$ ./gen-intervals | ./partition-intervals
Because gen-intervals creates a new interval set each time it's run, you might find it more convenient to save the intervals in a file to provide your program with consistent input: 
$ ./gen-intervals > intervals

$ ./partition-intervals < intervals

This page last modified on 15 February 2006.