给定时间段内重叠间隔的最大范围

Question

问题陈述

输入 : 一组间隔（开始时间和结束时间）和每 30 分钟每个元素的强度。

例如：

{00:00，01:30，5}

{01:00, 02:30, 10}

{00:30，02:30，2}

{01:00, 04:00, 3}

输出：最大重叠30分钟周期和重叠元素的强度总和。

对于上述输入，输出应该是01:00 - 01:30和强度 - 20（这里的强度是直接相加，因为所有元素都完全参与了最大重叠30分钟，它可能会有所不同对应最大区间的参与时间）。

简而言之，应该找到最大重叠 30 分钟以及该时段参与元素的增加强度。

可以看到不同线程回答最大重叠点和间隔，但找不到上述问题的解决方案。

任何建议都会有所帮助！

Answer 1

算法如下：

定义起点（所有起点的最小值）和终点（所有终点的最大值）点以找到范围
将范围分成 30 分钟的子间隔
计算每个 sub-interval
找到具有最大计算强度的 sub-interval。

使用 Java 8 Stream API 和自定义 class 的示例实现（为简洁起见，在几分钟内实现了起点和终点，无需解析“HH:MM”字符串）如下:

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

输出：

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

“无流式”实现可能如下：

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

给定时间段内重叠间隔的最大范围

Maximum range of overlapping interval for a given time period

java

sorting

algorithm

search

intervals