Programming Assignment 2

You are given n closed subintervals [a_i,b_i] of the real interval [0,1]. Your task is to locate the leftmost region of maximum overlap of the given intervals. The following figure illustrates this problem for ten intervals. In this example, the maximum overlap size is five, and this is achieved twice (shaded by green and pink). Only the leftmost region needs to be reported.

Write a program to do the following. First, read the number n of intervals from the user. Generate n subintervals of [0,1] with the two endpoints chosen uniformly randomly in the interval [0,1]. Report the following three items.

• The leftmost region of maximum overlap (this is again an interval).
• How many of the input intervals overlap with the maximum-overlap region.
• The indices of all the input intervals that overlap with the maximum-overlap region.

Your program should run in O(n log n) time in the worst case, and be as efficient as possible.

Notes

Consider the following points before you start coding.

• You can generate a random floating-point number in the interval [0,1] as:

     (double)rand() / (double)RAND_MAX
  

  You may seed the random number generator as:

     srand((unsigned int)time(NULL));
  

  Do this only once at the beginning of your main() function. Also, #include <time.h> which stores the prototype of the time() call. The calls rand() and srand() are declared in stdlib.h.

• A closed real interval [a,b] is the set of all real numbers x satisfying a <= x <= b. We should have a <= b. In the degenerate case when a = b, the interval is a single point. Avoid generating such degenerate intervals as input to your algorithm. However, your output may be a degenerate interval.

• The intersection (overlap) of the closed intervals [a,b] and [b,c] is the single point b, that is, the degenerate interval [b,b].

• Any subinterval (even a point) in the leftmost maximum-overlap interval is again a maximum-overlap interval. You should report the leftmost maximum-overlap interval as one which is as wide as possible.

• Any maximally wide overlap region starts at the left endpoint of an input interval and ends at the right endpoint of the same or another input interval. Moreover, no input interval starts or ends inside this maximally wide overlap region. These observations immediately lead to an O(n³)-time algorithm to solve the problem. You should do something better than following this naive approach.

Sample output

The above figure is drawn from the following randomly generated data.

   How many intervals? 10
   Interval      0 = [0.784384,0.962058]
   Interval      1 = [0.249457,0.473880]
   Interval      2 = [0.077236,0.294932]
   Interval      3 = [0.391598,0.686297]
   Interval      4 = [0.361750,0.647535]
   Interval      5 = [0.521847,0.989767]
   Interval      6 = [0.145509,0.249701]
   Interval      7 = [0.026383,0.145308]
   Interval      8 = [0.086777,0.577941]
   Interval      9 = [0.293653,0.925077]
   Leftmost maximum overlap is [0.391598,0.473880]
   Number of overlapping intervals is 5
   Indices of overlapping intervals are:
         1       3      4      8      9
   Number of indices printed is 5

Submission Site

---

Back | Home