Finding the Longest Gap Between Multiple Intervals

Finding the longest gap between multiple intervals

<?php

$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10]
];

$non_overlapping = [];
$start = -1;
$end = -1;

foreach($intervals as $index => $interval){
    if($start == -1) $start = $interval[0];
    if($end == -1) $end = $interval[1];

    if($index == 0) continue; // since it's first index

    if($interval[0] >= $end){
        $non_overlapping[] = [$start,$end];
        $start = $interval[0];
        $end = $interval[1];
    }else{
        $end = max($end,$interval[1]);
    }
}

$non_overlapping[] = [$start,$end];
$maximum_gap = 0;
$prev_end = 0;

foreach($non_overlapping as $index => $interval){
    $maximum_gap = max($maximum_gap,$interval[0] - $prev_end - 1);
    $prev_end = $interval[1];
}

$maximum_gap = max($maximum_gap,$n - $prev_end);

echo $maximum_gap;

• Since your intervals are sorted according to start time, we make a new array of non overlapping intervals.
• Now, we just subtract new start time with previous end time and at last also, last end time with $n itself and find the maximum gap.

How to correctly find intervals between other intervals

Turn intervals into pairs of start/end events, sort the events by time, then run through the list and keep a count of how many more start than end.

Any stretch of time where the two are equal becomes an interval in your answer.

---

Here is an explanatory example. Suppose we have the following intervals:

04:00 - 09:00
15:00 - 20:00
08:00 - 12:00

We get the following list of events from them.

04:00 start
09:00 end
15:00 start
20:00 end
08:00 start
12:00 end

Add 2 more to bookend the day

00:00 analysis_start
24:00 analysis_end

Which get sorted into:

00:00 analysis_start
04:00 start
08:00 start
09:00 end
12:00 end
15:00 start
20:00 end
24:00 analysis_end

And now we process them to come up with the following counts of open intervals:

00:00 - 04:00 0
04:00 - 08:00 1
08:00 - 09:00 2
09:00 - 12:00 1
12:00 - 15:00 0
15:00 - 20:00 1
20:00 - 24:00 0

And now the answer is where our tally was 0:

00:00 - 04:00
12:00 - 15:00
20:00 - 24:00

Find largest continuous interval such that all number between starting and ending are greater than starting and less than ending

We can solve this in O(n log n) by considering each element as the potential leftmost element in the interval. For each such candidate, (1) find the first element to the right that's lower than it - that's a bound on the right for the possible interval since including such an element would invalidate the constraints; (2) find the leftmost instance of the maximum element in the interval (or rightmost if A[j] is allowed to be equal to an element on its left) - that's the farthest right the interval could extend without invalidating the constraints.

We can store the answer for (1) for all elements in O(n), using a stack. We can preprocess a structure for range-maximum-query that would answer the first part of (2) in O(log n) time. Once the maximum for the interval is found, if we have an ordered list of its instances in the array (which we can preprocess in O(n) with a hash table), we can find the rightmost or leftmost occurrence of it in the interval in O(log n) time.

Python: How to find longest continuous interval with connected interval start and end

Dynamic programming:

from collections import defaultdict

intervals = [-4,1][1,5][2,10][3,5][1,3][3,8][8,12][5,11]
intervals = sorted(intervals, key=lambda x: (x[1], x[0]))  # will sort by end, then start

distances = defaultdict(int)
for start, end in intervals:
    # this is the key step: at each point, the max length interval up to here
    # is max combined length of all intervals that end here
    distances[end] = max(distances[end], distances[start] + end-start)
print(max(distances.values()))

Finding overlaps between millions of ranges/intervals

Here's an algorithm.

1. Prepare a set of intervals sorted by starting point. Initially the set is empty.
2. Sort all starting and ending points.
3. Traverse the points. If a starting point is encountered, add the corresponding interval to the set. If an ending point is encountered, remove the corresponding interval from the set.
4. When removing an interval, look at other intervals in the set. They all overlap the interval being removed, and they are sorted by the length of the overlap, longest first. Traverse the set until the length is too short, and report each overlap.

Maximum range of overlapping interval for a given time period

The algoritm is as follows:

1. Define start (min of all starts) and end (max of all ends) points to find a range
2. Split the range into 30-min subintervals
3. Calculate total strength for each sub-interval
4. Find the sub-interval with maximum calculated strength.

Example implementation using Java 8 Stream API and a custom class (start and end points implemented in minutes without parsing "HH:MM" string for brevity) is as follows:

public class IntervalStrength {
    private final int start; // inclusive
    private final int end;   // exclusive
    private final int strength;
        
    public IntervalStrength(int start, int end, int strength) {
        this.start = start;
        this.end = end;
        this.strength = strength;
    }
        
    public int getStart() { return start; }
    public int getEnd() { return end; }
    public int getStrength() { return strength; }
        
    public String toString() {
        return String.format("[%02d:%02d, %02d:%02d] - %d", 
            start / 60, start % 60, end / 60, end % 60, strength);
    }
}

import java.util.*;
import java.util.stream.*;

public class Main {
    private static final int HALF_HOUR = 30;
    public static void main(String args[]) {
        List<IntervalStrength> data = Arrays.asList(
            new IntervalStrength(0, 90, 5),
            new IntervalStrength(60, 150, 10),
            new IntervalStrength(30, 150, 2),
            new IntervalStrength(60, 240, 3)
        );
        int start = data.stream().mapToInt(IntervalStrength::getStart).min().getAsInt();
        int end = data.stream().mapToInt(IntervalStrength::getEnd).max().getAsInt();
        System.out.println(start + ", " + end);
        
        IntervalStrength strongest = IntStream
            .iterate(start, t -> t < end - HALF_HOUR, t -> t + HALF_HOUR)
            .mapToObj(t -> new IntervalStrength(  // create sub-interval
                    t, t + HALF_HOUR, // start and end of sub-interval
                    data.stream()     // find overlapping
                        .filter(d -> d.getStart() <= t && d.getEnd() >= t + HALF_HOUR)
                        .mapToInt(IntervalStrength::getStrength)
                        .sum()  // calculate sum of strengths
            ))
            // find max strength of sub-interval
            .max(Comparator.comparingInt(IntervalStrength::getStrength))
            .get();  // retrieve sub-interval
                 
        System.out.println(strongest);
        
    }
}

Output:

0, 240
[01:00, 01:30] - 20

---

"Streamless" implementation may be as follows:

public static IntervalStrength findSubintervalMaxStrength(List<IntervalStrength> data) {
    int start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
        
    for (IntervalStrength interval : data) {
        if (interval.getStart() < start) start = interval.getStart();
        if (interval.getEnd() > end) end = interval.getEnd();
    }
        
    System.out.println(start + ", " + end);
        
    int maxStrength = 0;
    int maxIntervalStart = start;
    for (int t = start; t <= end - HALF_HOUR; t += HALF_HOUR) {
        int subintervalStrength = 0;
        for (IntervalStrength interval : data) {
            if (interval.getStart() <= t && interval.getEnd() >= t + HALF_HOUR) {
                subintervalStrength += interval.getStrength();
            }
        }
        if (maxStrength < subintervalStrength) {
            maxStrength = subintervalStrength;
            maxIntervalStart = t;
        }
    }
    return new IntervalStrength(maxIntervalStart, maxIntervalStart + HALF_HOUR, maxStrength);
}

---

Related Topics