This discussion is archived
13 Replies Latest reply: Dec 13, 2012 7:49 AM by Alex Geller RSS

Looking for overlapping algorithm

978140 Newbie
Currently Being Moderated
Hi. Any idea if there is any appropriate algorithm for calculating time without overlaps in a collection of time intervalls? Having hard time to solve this.

Example:
[start, end]
Time intervalls: [2,3], [4,7], [1,6]
Result: 6

Guess I should start with sorting them in start time. But what then?
  • 1. Re: Looking for overlapping algorithm
    TPD-Opitz-Consulting-com Expert
    Currently Being Moderated
    your requirement is not clear to me.

    what's the real question?
    why is 6 the correct answer?
    by changing parameters in the question: is there a possibility that 7 is the correct answer?
    when you add more examples, when would the correct answer change?

    bye
    TPD
  • 2. Re: Looking for overlapping algorithm
    978140 Newbie
    Currently Being Moderated
    Ok. Lets try again:
    Q: You are having a collection of random time intervalls with start and end time, [start time, end time]. What is the total time without counting two or more intervalls in the same time slot twice?

    Example 1:
    E1: [1,2], [2,3], [3,4]
    Ans: 1+1+1 = 3

    E2: [1,2], [2,4], [3,4]
    The time slot [3,4] is overlapping [2,4] and dismissed:
    Ans: 1+2 = 3

    E3: [1,10], [20,25], [21,30], [28,30]
    First time slot[1,10] is not overlapping with anything = 9
    Second time slot[20,25] is overlapping with [21,30]. 20 it not overlapping(+1), 21-25 is overlapping(+4, the thing is that we only add the time for this timeslot once) and 25-30 it not overlapping(+5) = 10
    Last time slot [28,30] is overlapping with [21,30]. Because already have been taking the time for [28,30] = 0
    Ans: 9 + 1 + 4 + 5 + 0 = 19

    Think I made it more clear now?
  • 3. Re: Looking for overlapping algorithm
    796283 Newbie
    Currently Being Moderated
    Have you tried putting all the intervals on a "number line" and just +1 when you find a 1 minute slot that's occupied?
  • 4. Re: Looking for overlapping algorithm
    978140 Newbie
    Currently Being Moderated
    Think what you are suggesting is having a time complexity of O(n^2). Would need a more general solution it think.
  • 5. Re: Looking for overlapping algorithm
    796283 Newbie
    Currently Being Moderated
    Then put it in a map and get the size of the keyset. What's the difference between O(n) and O(n ^2^ ) when you don't have any solution to begin with?
  • 6. Re: Looking for overlapping algorithm
    978140 Newbie
    Currently Being Moderated
    I can start with what I have come up with:
    result = total time for all intervalls
    List list = sort intervalls with earliest starttime first
    first starttime : t1
    for all start times
       next starttime : t2
       if t1 ends before t2 ends
          if t1 starts before t2 ends
            remove (t1 end - t2 start) from result
          else no overlap and do nothing
       else t2 ends before t1 ends
           remove t2 end - t2 start from result
       set t1 = t2
    I think this is correct as long as we dont have two(or more) intervalls that starts before an earlier intervall has ended.
    Example: sorted list with intervalls [a,b,c].
    Gives wrong if a end time is bigger then both b and c start times
  • 7. Re: Looking for overlapping algorithm
    rp0428 Guru
    Currently Being Moderated
    >
    I think this is correct as long as we dont have two(or more) intervalls that starts before an earlier intervall has ended.
    Example: sorted list with intervalls [a,b,c].
    Gives wrong if a end time is bigger then both b and c start times
    >
    Your key constraint in your use case is that ANY pair can overlap any OR ALL of the other pairs. That means that each pair, after sorting by start time, must be checked against ALL previous pairs: the third pair must be checked again the first two, the fourth against the first three and so on.

    1. Put the first pair into the result set - there is no need to SORT the pairs you start with; it is the result set of pairs that needs to be in order.
    2. for each pair in the remaining list
    a. for each pair in the result list
    1) if the new pair does NOT overlap the result pair continue (loop to next result pair)
    2) the new pair overlaps
    a) if the pair overlaps completely do nothing - this interval is already covered - continue the OUTER loop (go to step 2)
    b) the new pair overlaps. You need to create a new pair for the part of the interval of the new pair that does NOT overlap the result pair. These new pairs (there will be either one or two) must be added to the SOURCE list; do NOT add them to the result since they may overlap other pairs already in the result.. You could use a recursive function for this loop and then just call it for the pair.

    So basically you put the first new pair into the result set. For each of the other pairs you check against each of the pairs already in the result set. Use a recursive function for this.

    If the new pair does not overlap you just add it. If it overlaps you create one or two new pairs to represent the non-overlapping intervals and call the recursive function for each of these to add them to the result list.

    Walk it through on paper first so you can follow the logic.
  • 8. Re: Looking for overlapping algorithm
    aksarben Journeyer
    Currently Being Moderated
    Another approach, which take da little more up front work, but is more useful in the long run (IMHO), is to create a time span class which implements a Mergeable interface. I have done something similar at my job when I needed to merge a list of (possibly adjacent) milepost ranges. Once a class implemented my Mergeable interface, I then called a list utility class with a merge() method that merged any objects in the list which abut each other.

    You could use the same approach on a list of time spans. Once they are merged so there are no overlaps, it would be simple to iterate thru the list, computing the duration of each time span & adding it a total.
  • 9. Re: Looking for overlapping algorithm
    baftos Expert
    Currently Being Moderated
    Maybe I use other words or use a technique similar to what others said, but here it is.
    Let's say we have an Interval class that encapsulates two numbers: start and end. Assume you know how to write a Interval merge(Interval i1, Interval i2) method that returns the merged interval or null, if the two are not mergeable.
    Now here is the skeleton of adding a new Interval to a List<Interval>.
    List<Interval> add(List<Interval> intervals, Interval newInterval) {
        for (Interval i : intervals) {
            Interval m = merge(newInterval, i);
            if (m != null) {
                 intervals.remove(i);
                 newInterval = m;
            }
         }
         intervals.add(newInterval);
         return intervals;
    }
    Call the above method in a loop for each interval in your input.

    Edit: Consider the above to be pseudo-code. A List.iterator() should be used instead of the for loop above for correct results.


    Edited by: baftos on Dec 12, 2012 2:02 PM
  • 10. Re: Looking for overlapping algorithm
    TPD-Opitz-Consulting-com Expert
    Currently Being Moderated
    how about this?
    /**
     * @author TPD, OPITZ-CONSULTING Deutschland GmbH
     * @version $Revision: $ $Date: $
     */
    public class IntervalMergerTest {
        private static final class Interval implements Comparable {
            private final int _x;
            private final int _y;
            Interval(int x, int y) {
                _x = x;
                _y = y;
            }
            public Interval merge(Interval otherInterval) {
                int x = _x < otherInterval._x ? _x : otherInterval._x;
                int y = _y > otherInterval._y ? _y : otherInterval._y;
                return new Interval(x, y);
            }
            public int getDuration() {
                return (_y - _x);
            }
            @Override
            public String toString() {
                return MessageFormat.format("Interval [_x={0}, _y={1}]", _x, _y);
            }
            @Override
            public int compareTo(Interval pO) {
                return _x == pO._x ? (_y - pO._y) : (_x - pO._x);
            }
        }
        Interval mergeIntervals(List<Interval> intervalls) {
            assert(!intervalls.isEmpty());
            TreeSet<Interval> orderedIntervals = new TreeSet<>(intervalls);
            Interval spanningInterval = orderedIntervals.first();
            for (Interval interval : orderedIntervals) {
                spanningInterval = spanningInterval.merge(interval);
            }
            return spanningInterval; 
        }
        @Test
        public final void testintervalMerge() {
            List<Interval> intervalls = new ArrayList<>();
            intervalls.add(new Interval(2, 3));
            intervalls.add(new Interval(4, 7));
            intervalls.add(new Interval(1, 6));
            Interval spanningInterval = mergeIntervals(intervalls);
            Assert.assertEquals("overall duration calculated", 6, spanningInterval.getDuration());
        }
    }
    the <tt>merge</tt> method should thow an exception if the otherInterval is disjunced, so that the caller can decide what to do (eg. adding the current spanningInterval to a list and set the faild as new spanningInterval ...).
    bye
    TPD

    Edited by: TPD Opitz-Consulting com on 13.12.2012 13:26

    Edited by: TPD Opitz-Consulting com on 13.12.2012 13:33
  • 11. Re: Looking for overlapping algorithm
    Alex Geller Newbie
    Currently Being Moderated
    if I am not mistaken, it fails on test E3 yielding 29 when it should yield 19:
                List<Interval> intervalls = new ArrayList();
                intervalls.add(new Interval(1, 10));
                intervalls.add(new Interval(20, 25));
                intervalls.add(new Interval(21, 30));
                intervalls.add(new Interval(28, 30));
                Interval spanningInterval = mergeIntervals(intervalls);
                Assert.assertEquals("overall duration calculated", 19, spanningInterval.getDuration());
  • 12. Re: Looking for overlapping algorithm
    TPD-Opitz-Consulting-com Expert
    Currently Being Moderated
    Alex Geller wrote:
    if I am not mistaken, it fails on test E3 yielding 29 when it should yield 19:
    This is true because (as I wrote) <tt>Interval</tt> does not (yet) check if the other interval is disjuct. So it simply add it (and the gap between...)
    You should implement that check and add the current <tt>spanningInterval</tt>s duration to not yet existing <tt>allIntervallsDuration</tt>.
    int allIntervallsDuration=0;
    Interval spanningInterval = orderedIntervals.first();
    for (Interval interval : orderedIntervals) {
       if(spanningInterval.isDisjunct(interval){
          allIntervallsDuration += spanningInterval.getDuration();
          spanningInterval = interval;
       } else {
          spanningInterval = spanningInterval.merge(interval);
       }
    }
    // don't forget the last interval. 
    allIntervallsDuration += spanningInterval.getDuration();
    // change the method to return the allIntervallsDuration and don't forget to give it a new name.
    bye
    TPD
  • 13. Re: Looking for overlapping algorithm
    Alex Geller Newbie
    Currently Being Moderated
    Yes very good. That works nicely and makes sense.

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points