Friday, April 16, 2010

Set of intervals

Given a set of intervals and on interval i, return the set of all the intervals overlapping with i in optimal time

1 comment:

  1. If I have got the question correctly, doesn't checking whether 2 intervals overlap a O(1) operation. Checking for the 4 possibilities should do the work. So just iterate over all the given intervals and check in O(1) if they overlap with the given interval.

    Please correct me if I have missed something.

    ReplyDelete