Re: Need efficient search strategy in list of time intervals

I have created an SSCCE for this problem:
------------------------------------------------------------------

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
 * A simple short self-contained compilable example (SSCCE), which
illustrates
 * the time span search problem.
 *
 * @author Dirk Lemmermann
 */
public class TimeSpanProblem {
    private List<TimeSpan> list = new ArrayList<TimeSpan>();

    private TimeSpanProblem() {
        // One huge time span that contains the other three spans.
        list.add(new TimeSpan(0, 70));

        // Three contained time spans.
        list.add(new TimeSpan(10, 20));
        list.add(new TimeSpan(30, 40));
        list.add(new TimeSpan(50, 60));

        // Sort all spans based on their start time.
        //
        // actually not needed because we added the time spans in their
        // correct order.
        Collections.sort(list);

        /*
         * find the first visible time span contained in interval 25, 80.
The
         * first one should be the huge time span 0, 70 but the binary
search
         * stops looking 'to the left' because interval 10, 20 is
         */
        int first = getFirstContainedSpan(new TimeSpan(25, 80));
        System.out.println("first contained time span = " + first);

        if (first != 0) {
            System.err.println("Time span problem not solved!");
            System.err.println("The huge time span that overlaps the");
            System.err.println("other three spans was not found.");
        }
    }

    public int getFirstContainedSpan(TimeSpan span) {
        /*
         * These are the javadocs of the binarySearch() method:
         *
         * Returns: the index of the search key, if it is contained in the
list;
         * otherwise, (-(insertion point) - 1). The insertion point is
defined
         * as the point at which the key would be inserted into the list:
the
         * index of the first element greater than the key, or list.size()
if
         * all elements in the list are less than the specified key. Note
that
         * this guarantees that the return value will be >= 0 if and only if
the
         * key is found.
         */
        int result = Collections.binarySearch(list, span);
        return -(result + 1);
    }

    class TimeSpan implements Comparable<TimeSpan> {
        long start;

        long end;

        public TimeSpan(long start, long end) {
            this.start = start;
            this.end = end;
        }

        public int compareTo(TimeSpan otherSpan) {
            long delta = otherSpan.start - start;
            if (delta > 0) {
                return -1;
            } else if (delta < 0) {
                return +1;
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        new TimeSpanProblem();
    }
}

--Dirk