That sounds like a job for a binary search.
See http://mindprod.com/jgloss/binarysearch.html

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

Why iterate? The next element can't be assumed to be hit by TS, so you
might have to iterate over a long list of irrelevant objects anyway.

This is equivalent to (A.end >= TS.start && A.start <= TS.end).
I expect that A.start <= A.end (and likewise for TS) can be assumed.

That sounds like "overlaps", not "contained in". Example;
TS = [2,4]
A = [1,3]
satisfies the requirement.

Sounds unlikely, at least in the worst case, since the end-points are
completely unordered. Worst case, assume a (long) list with same start
time, and only one interval has a large enough end time to overlap the
TS.

You should consider whether there is a better data structure than a list
for your purpose, to account for both start and end time.
I can't think of a one, but why think when you can google (for "time interval
data structure"). It seems an Interval Tree is what you need:
<URL:http://en.wikipedia.org/wiki/Interval_tree>.
Found this too:
<URL:http://i11www.iti.uni-karlsruhe.de/~awolff/map-labeling/design/old/interfaces/ge
n_interval_tree.ps>

Good luck
/L

Predigest your list so that you decide which band number you want for
any point on the line. You can create dummy bands to handle areas not
covered. Then you need do your binary search only on the start points
of each band.  You look for a band start point <= to the search point.
Have a look inside com.mindprod.jdisplay.PrettyCanvas. It does this.
http://mindprod.com/products.html#JDISPLAY

Does the start time of the probe interval ever reduce? If not, consider
the following:

Keep the intervals in a doubly linked list, such as
java.util.LinkedList, sorted in ascending order of start time.

For each search, scan the list from the start.

If the start time is greater than the probe end time, stop. You have
found all the overlaps for this probe.

Else if the end time is less than the probe start time, delete the interval.

Any interval that passes both those tests overlaps the probe. Each
interval is operated on at most once after it becomes irrelevant, and
otherwise you only look at one non-hit.

The harder problem is if the interface start time can reduce. If so,
perhaps you should think of your intervals as points in a two
dimensional space, indexed by start and end time. The probe interval is
a rectangular region of that space. Look at R-tree, KD-tree etc. to see
if there is something that helps.

Patricia

I've had to do this myself recently.  What I did was created a class
that represented an Instant (either start or end), and a collection of
all spans that were in the instant (it took some time to build this
index for large datasets), the collection of Instants and be sorted,
and the you can do a binary search for the Instant.  This worked
pretty well, but it did take some extra time to build the indexes.

I had a few other ideas that I haven't tried yet.  One was to use
Lucene to build an index of my data.

The other was to keep track of the maximum interval size, sort the
intervals by start, binary search for a value, and then move backward
until the start + maxInterval < searchStart;  This approach is
dependent on the data a little more, one long interval can cause a big
slow down.

Depending on your dataset size, it might actually be fast enough just
to do a linear search.

Dirk,

I recently discussed the same thing in another post -- mapping ranged
values to 1 value. You can do it, and I will cross link you, but there
are caveats dealing with "comparable". The implementation I provided
in the groups is safe and works fine but it has limits (mainly because
I haven't worked past them).

Here is the link to the other post
http://groups.google.com/group/comp.lang.java.programmer/browse_thread/thread/d4
ae3db72482546b/edbf219682de8458#edbf219682de8458

It is, as others have suggested, based on a b-tree.

Christian Bongiorno
http://christian.bongiorno.org