CODEWITHSUNDEEP
phpalgorithm
ringpull
ringpull

Reputation: 51

Find largest sets of consecutive time periods

I have an array of time periods on a given day, where some overlap, like so (start, end):

(10.00, 10.15) (11.00, 11.30) (11.30, 11.45) (11.45, 12.00) 
(11.45, 12.15) (12.15, 12.45) (13.20, 13.30) (14.15, 14.35) (14.35, 14.40)

I want to find the largest sets of consecutive time periods. In the above example there are 3 sets of consecutive times (shown below) but as the first set is a smaller 'alternative' to the second it should be ignored, so we are left with 2 and 3.

  1. 11.00 - 11.30, 11.30 - 11.45, 11.45 - 12.00
  2. 11.00 - 11.30, 11.30 - 11.45, 11.45 - 12.15, 12.15 - 12.45
  3. 14.15 - 14.35, 14.35 - 14.40

One thing I must add: I would like to be able to specify a 'tolerance' that defines what consecutive means. In the above example consecutive means end time of first time period == start time of next time period, but it would be great to define consecutive as time periods that are '5 minutes apart', say.

Any ideas on how to do this in php or pseudocode would be greatly appreciated!

Upvotes: 2

Views: 281

Answers (2)

Sabbir Yousuf Sanny
Sabbir Yousuf Sanny

Reputation: 594

There is an easy greedy solution for this problem. First sort the time periods by start date ascending and if equal then by end date descending. Now loop through the time periods and keep track of your current set (it's leftmost and rightmost position). Here's the pseudo code (or some PHP / C++ / JS mix) -

bool comp(A, B) {
    if(A.start == B.start) return A.end > B.end;
    return A.start < B.start;
}

function getLongestSet( periods ) { //convert the times to integer first, period is pair of integers
    sort ( periods, comp);
    longestPeriod = 0;
    for(i = 0; i < periods.length; i++) {
        if(periods[i].start > curRight + TOLERANCE) { //start new set
            curLeft = periods[i].start, curRight = periods[i].end;
        }
        else { //expand current set
            curRight = max(curRight, periods[i].end);
        } 
        longestPeriod = max(longestPeriod, curRight - curLeft);
    }
    return longestPeriod;
}

Upvotes: 0

zmbq
zmbq

Reputation: 39023

This feels like a Dynamic Programming kind of problem. I guess it can be solved as a graph problem, too.

If you turn your data into a graph: each period is a vertex, two vertices are connected if they are consecutive (use whatever tolerance level you want for this). All edges have the same weight. Now you need to find the longest path on that graph.

The longest path problem is an NP-complete, which is a bummer. However, with graphs without cycles, it is possible to solve this in polynomial time. Cool. Your graph is a-cyclic I hope (you don't round around entire days, right?). So, just put a weight of -1 on each edge, and find the shortest graph. The last link I supplied also has a dynamic programming approach for this.

Upvotes: 2

Related Questions