Maximum range of overlapping interval for a given time period

Question

Problem Statement

Input : Set of intervals (start time and end time) and strength of each element per 30 minutes.

Eg:

{00:00, 01:30, 5}

{01:00, 02:30, 10}

{00:30, 02:30, 2}

{01:00, 04:00, 3}

Output : The maximum overlapping 30 minutes period and sum of strength of overlapping elements.

for the above input, output should be 01:00 - 01:30 and strength - 20 (Strength here is direct sum since all elements have participated fully in the max overlapping 30 mins, it may vary corresponding to the participation time in the max interval).

In simple words, the max overlapping 30 mins should be found along with the added strength for that period of participating elements.

Could see different threads answering max overlapping point and interval, but couldn't find a solution for the above.

Any suggestions will help!

Answer 1

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);
}