java - 使用 RangeMap 时相交范围

Question

我遇到了这样的问题

您正在维护一个对冲基金的交易平台。您的对冲基金的交易员全天执行交易策略。为了简单起见，我们假设每个交易策略在运行期间每分钟赚取 i 磅。 i 可以是负数。在一天结束时，您会得到一个如下所示的日志文件:

• timestamp_start_1, timestamp_end_1, i_1
• timestamp_start_2, timestamp_end_2, i_2
• timestamp_start_3, timestamp_end_3, i_3

每条线代表策略开始执行的时间、停止执行的时间以及产生的收入(以比率表示)。编写一些代码以返回对冲基金每分钟赚取最高金额的那一天的时间。

例子:

输入:

• (1, 13, 400)
• (10, 20, 100)

结果:

• (10,13) 500

输入:

• (12,14, 400)
• (10,20,100)

结果:

• (12,14) 500

输入:

• (10, 20, 400)
• (21,25,100)

结果:

• (10,20) 400

我一直在尝试使用 guava RangeMap 来解决它，但是没有明显的方法可以使重叠区间相交。

例如:

private static void method(Record[] array){
    RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
    for (Record record : array) {
        rangeMap.put(Range.closed(record.startTime, record.endTime), record.profitRate);
    }
    System.out.println(rangeMap);   
}

public static void main(String[] args) {
    Record[] array = {new Record(1,13,400), new Record(10,20,100)};
    method(array);
}

map 看起来像:[[1..10)=400, [10..20]=100]

有没有办法覆盖重叠行为或任何其他可用于解决问题的数据结构？

Answer 1

使用 RangeMap.subRangeMap(Range) 来识别所有与其他特定范围相交的现有范围条目，这将允许您过滤掉交叉点。

这可能看起来像:

void add(RangeMap<Integer, Integer> existing, Range<Integer> range, int add) {
  List<Map.Entry<Range<Integer>, Integer>> overlaps = new ArrayList<>(
      existing.subRangeMap(range).asMapOfRanges().entrySet());
  existing.put(range, add);
  for (Map.Entry<Range, Integer> overlap : overlaps) {
    existing.put(overlap.getKey(), overlap.getValue() + add);
  }
}