CS 176 Lab Assignment 4

CS 176, Introduction to Computer Science II

Lab Assignment 4 Answer

This program is supposed to determine if two intervals overlap. An extreme case of two intervals overlapping occurs at the endpoints: what happens if the two intervals share only an endpoint?

$ g++ -o la4 la4.cc

$ la4
Input four integers:  1 3 3 5
The interval [1, 3] does not overlap with the interval [3, 5].
Input four integers:

That didn't work. The most likely place to look for the error is in overlapping(), and sure enough, the test for overlapping only checks to see if the second interval is contained entirely within the first interval:

return ((iarray[0] <= iarray[2]) && (iarray[2] <= iarray[1])) && 
       ((iarray[0] <= iarray[3]) && (iarray[3] <= iarray[1]));

What should the proper test be? The easiest and surest way to determine the proper cases is to examine all the possible cases:

What characterizes the overlapping intervals? It seems easier to characterize the non-overlapping intervals; if two intervals are not non-overlapping, then tney must be overlapping.

From the picture, two intervals are non-overlapping if the smallest value in the second interval is greater than the largest value in the first interval (top interval pair) or if if the largest value in the second interval is less than the smallest value in the first interval (bottom interval pair) or

return !((iarray[1] < iarray[2]) || (iarray[3] < iarray[0]))

Making this change to overlapping() seems to do the trick:

$ g++ -o la4 la4.cc

$ la4
Input four integers:  1 3 3 5
The interval [1, 3] overlaps with the interval [3, 5].
Input four integers:  1 3 -1 1
The interval [1, 3] overlaps with the interval [-1, 1].
Input four integers:

That seems to work; let's try one more:

Input four integers:  5 1 3 2
The interval [5, 1] does not overlap with the interval [3, 2].
Input four integers:

Ah well. Looking at the intervals entered and the test in overlapping(), the problem soon becomes clear: the intervals are entered backward. That is, overlapping() implicitly assumes that iarray[0] <= iarray[1] and iarray[2] <= iarray[2]. Had we been paying attention, we might have caught this earlier when talking about comparing the largest and smallest values in the intervals.

The fix for this is a bit tricky because iarray is const and so can't be changed. While we can delete the const qualifier, it's not a good idea to change the interface (especially when the change makes the interface less secure); instead we'll make a copy of the input array, ordering the elements as their being copied:

static bool overlapping(const int iarray[]) {

  // Return true if the interval [iarray[0], iarray[1]] overlaps with the
  // interval [iarray[2], iarray[3]].  Two intervals overlap if at least one
  // integer appears in both intervals.

  int ia[4];

  copy_and_swap(ia, iarray, 0);
  copy_and_swap(ia, iarray, 2);

  return !((ia[1] < ia[2]) || (ia[3] < ia[0]));
  }

where copy_and_swap() is

static void copy_and_swap(int to[], const int from[], int i) {

  // Store the smaller of the two values from[i] and from[i + 1] in to[i];
  // store the larger of the two values from[i] and from[i + 1] in to[i + 1].

  if (from[i] <= from[1]) {
    to[i] = from[i];
    to[i + 1] = from[i + 1];
    }
  else {
    to[i] = from[i + 1];
    to[i + 1] = from[i];
    }
  }

And that does it:

$ g++ -o la4 la4.cc

$ la4
Input four integers:  1 3 3 5
The interval [1, 3] overlaps with the interval [3, 5].
Input four integers:  -1 1 1 3
The interval [-1, 1] overlaps with the interval [1, 3].
Input four integers:  5 1 4 2
The interval [5, 1] overlaps with the interval [4, 2].
Input four integers:

This page last modified on 18 July 2001.