英文:
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
算法如下:
- 定义起始点(所有起始点中的最小值)和结束点(所有结束点中的最大值)以找到一个范围。
- 将范围分割为30分钟的子区间。
- 计算每个子区间的总强度。
- 找到计算强度最大的子区间。
示例实现使用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:
- Define start (min of all starts) and end (max of all ends) points to find a range
- Split the range into 30-min subintervals
- Calculate total strength for each sub-interval
- 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);
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论