> Uh, no, it wouldn't. Visually:
>
> L1 -------------------------
> L2 -----------
> L3 ---------------------
>
> R1 --------
>
> At L2, you'd conclude that you're done matching R1.
>
No, you should conclude that you're done matching L2. You conclude
you're done matching R1 when you reach L4 ( or there exists a j st
Lj.start > R1.end, or equivalently Lj is strictly greater than R1 )
FWIW, this is a very common problem in bioinformatics. I've mostly
implemented this in python and C. The code is available at
encodestatistics.org. Look in encode.py at the overlap method of the
feature_region class, or ( for the C version ) region_overlap in
block_bootstrap.c ( svn is more up to date for the C ).
-Nathan