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

huangapple go评论70阅读模式
英文:

Maximum range of overlapping interval for a given time period

问题

问题描述

输入:一组区间(起始时间和结束时间),以及每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分钟,以及参与元素在该时段的强度总和。

(代码部分不提供翻译。)

英文:

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!

答案1

得分: 1

算法如下:

  1. 定义起始点(所有起始点中的最小值)和结束点(所有结束点中的最大值)以找到一个范围。
  2. 将范围分割为30分钟的子区间。
  3. 计算每个子区间的总强度。
  4. 找到计算强度最大的子区间。

示例实现使用Java 8 Stream API和自定义类(起始和结束点以分钟为单位实现,为了简洁起见,不解析“HH:MM”字符串)如下:

public class IntervalStrength {
    private final int start; // 包含
    private final int end;   // 不包含
    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

“无Stream”实现如下:

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);
}
英文:

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(&quot;[%02d:%02d, %02d:%02d] - %d&quot;, 
            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&lt;IntervalStrength&gt; 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 + &quot;, &quot; + end);
        
        IntervalStrength strongest = IntStream
            .iterate(start, t -&gt; t &lt; end - HALF_HOUR, t -&gt; t + HALF_HOUR)
            .mapToObj(t -&gt; new IntervalStrength(  // create sub-interval
                    t, t + HALF_HOUR, // start and end of sub-interval
                    data.stream()     // find overlapping
                        .filter(d -&gt; d.getStart() &lt;= t &amp;&amp; d.getEnd() &gt;= 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&lt;IntervalStrength&gt; data) {
    int start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
        
    for (IntervalStrength interval : data) {
        if (interval.getStart() &lt; start) start = interval.getStart();
        if (interval.getEnd() &gt; end) end = interval.getEnd();
    }
        
    System.out.println(start + &quot;, &quot; + end);
        
    int maxStrength = 0;
    int maxIntervalStart = start;
    for (int t = start; t &lt;= end - HALF_HOUR; t += HALF_HOUR) {
        int subintervalStrength = 0;
        for (IntervalStrength interval : data) {
            if (interval.getStart() &lt;= t &amp;&amp; interval.getEnd() &gt;= t + HALF_HOUR) {
                subintervalStrength += interval.getStrength();
            }
        }
        if (maxStrength &lt; subintervalStrength) {
            maxStrength = subintervalStrength;
            maxIntervalStart = t;
        }
    }
    return new IntervalStrength(maxIntervalStart, maxIntervalStart + HALF_HOUR, maxStrength);
}

huangapple
  • 本文由 发表于 2020年9月24日 02:23:34
  • 转载请务必保留本文链接:https://go.coder-hub.com/64034115.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定