Assignment 3

In this assignment you will be working on two data structures that store a set of intervals.  An interval has a left endpoing, a, and a right endpoint, b, with a <= b (as defined by Interval.compareTo()).
  1. This question asks you to complete the implementation of the DisjointIntervalSet class, which stores a disjoint set of Intervals in a SortedSet. This means that you should
    1. complete the implementation of the contains(x) method, which determines if any interval in the set contains x. See the example in Interval.main() to see how this can be done efficiently when the intervals are stored in a TreeSet.
    2. complete the implementation of the add(i) method, which adds the interval i to the set, provided that i does not overlap any interval already in the set. Note, your code should not significantly increase the cost of adding i to the set.
  2. This is a continuation of Part 1. Complete implementation of the OverlappingIntervalSet class. This class is just like DisjointIntervalSet, but it allows the user to add intervals that overlap intervals already in the set. Note that a SortedSet can not store two intervals if they overlap (since the compareTo() method can't say that one interval is less than the other). Therefore, for this question, you will have to trim and/or remove intervals that are already in the set if they overlap the interval that is being added.Note - Once completed, the add(i) and contains(x) methods in this class should be as fast as the DisjointIntervalSet class. Both classes (DisjointIntervalSet and OverlappingIntervalSet) should be much much faster than the DumbIntervalSet class.
Powered by