Get a list of overlapping time ranges from a set of appointments

Question

Title isn't great, and I'm open to suggestions.

Here's my basic problem:

I have a set of appointments, each with a start time and end time.

Given that set, what I want is a new set of ranges [ start_time, end_time ] for all periods where there are n overlapping appointments.

So, for example, given the set (timestamps simplified to small numbers for readability)

[ [ 1, 3 ], [ 2, 4 ], [ 2, 4 ], [ 5, 7 ], [ 6, 8 ], [ 7, 8 ] ]

...and assuming I want all ranges that have at least 3 different appointments occurring within them, the result should be

[ [ 2, 3 ], [ 6, 7 ] ]

To make this a bit less abstract...

Imagine I run a 24-hour window-tinting service with 3 installers on staff at all times. On my website, I want to show all available installation times. So I need to hide any time ranges where I've already got 3 appointments scheduled.

Not necessarily asking anyone to write code – but if there's a well-known algorithm for this class of problem that someone could point me to, I'd appreciate it.

Thanks.

[EDIT] added javascript tag because i'll be implementing this in Node, but answers don't need to be in JS.

[EDIT 2] I'm looking for a pretty general solution, so let's say that appointments can start at any time (not normalized to hour or 30 minute chunks) and can be of any duration

Answer 1

I think it works to create a histogram from the input ranges, then iterate through the histogram locating ranges where the height is greater than or equal to your target overlap, in this case 3.

BTW, I don't think [6,7] is a valid range given your inputs - I believe it should be [7,7]. At least that's what my code produces :)

Here's some Java code to illustrate:

public static void main(String[] args)
{
    int[][] ranges = {{1,3},{2,4},{2,4},{5,7},{6,8},{7,8}};

    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(int[] range : ranges) 
    {
        min = Math.min(min, range[0]);
        max = Math.max(max, range[1]);
    }       

    int[] hist = new int[1+max-min];
    for(int[] range : ranges) 
        for(int i=range[0]; i<=range[1]; i++) hist[i-min]++;

    int overlap = 3;
    for(int i=0; i<hist.length; i++)
    {
        int j = i;
        while(i<hist.length && hist[i] >= overlap) {i++;}
        if(i>j) 
            System.out.println((j+min) + " : " + (i+min-1));
    }
}

Output:

2 : 3
7 : 7

EDIT

I was dissatisfied with histogram approach since it relies on integer ranges and would be inefficient for long ranges. It occurred to me that you could instead sort the range endpoints, keeping track of whether they were at the start or end of the range, then walk through the endpoints keeping a counter of active ranges (increment when you encounter a start, decrement when you encounter an end). When the counter first rose above or fell below your threshold, in your case 3, you'd output the range.

I now see that MBo suggested this same approach.

Here's some more code to illustrate:

static class RangeEnd
{
    int time;
    int delta;
    public RangeEnd(int pos, int delta)
    {
        this.time = pos;
        this.delta = delta;
    }
}

public static void main(String[] args)
{
    int[][] ranges = {{ 1,3},{2,4},{2,4},{5,7},{6,8},{7,8}};

    RangeEnd[] ends = new RangeEnd[2*ranges.length];

    int i=0;
    for(int[] range : ranges) 
    {
        ends[i++] = new RangeEnd(range[0], 1);
        ends[i++] = new RangeEnd(range[1], -1);
    }

    Arrays.sort(ends, new Comparator<RangeEnd>()
    {

        @Override
        public int compare(RangeEnd e1, RangeEnd e2)
        {
            if(e1.time < e2.time) return -1;
            else if(e1.time > e2.time) return 1;
            else if (e1.delta > e2.delta) return -1;
            else return 1;
        }
    });

    int overlap = 3;

    int count = 0;
    boolean active = false;
    int start = 0;
    for(RangeEnd end : ends)
    {
        count += end.delta;
        if(count >= overlap)
        {
            if(!active)
            {
                start = end.time;
                active = true;
            }
        }
        else if(active)
        {
            System.out.println(start + " : " + end.time);
            active = false;
        }
    }
}

Answer 2

Make array/list of pairs: {time, flag = +1 for start of interval, -1 for the end of interval}

Sort list by time key. In case of tie account for start/end flag (end before start if intervals like [1,2] and [2,3] should not intersect)

Make Counter = 0

Traverse list, for every pair add flag to Counter. When Counter changes from n-1 to n - output range begins, when Counter changes from n to n-1 - output range ends

Answer 3

Assuming you can place things, say, on 30 minute intervals, then just start at first interval with #appts=0, and at every interval point, increment for every appt starting now and decrement for every appt ending now. #appts will always track how many appts are active at the current interval.

If you want to be really crazy efficient, you can "bucket sort" your starting end ending times into buckets for each interval, then the whole process will be linear. But unless you have a super large number of appointments, it will also work to just look them up as you go along.

Answer 4

What do your time stamps and ranges look like exactly? Are they daily/ hour / half hour / minute specific?

Here's a possible solution: Let's say your time stamps are hour specific. Declare a dictionary to hold a string key and int value. Key will represent time stamp to the hour e.g. "08-30-17 23". Value will be the count of how many appointments will be/are taking place in that hour.

Now Loop through your set of ranges. For each range, use another loop to go through the hours between the start and end time. For each of those hours, increment the count by 1 in the dictionary for that time stamp (with hour granularity).

At the end you should have the number of appointments taking place for every hour found in your data. If you have three appointments between 5 and 6pm and also 6 and 7pm of a given day then you'll need some more logic to transform that into a 5 to 7pm range.