以长度为3的数组存放时间段及该时间段的酒店平均价格,如{10, 30, 300}表示10-30时间段内,平均价格为300。时间段可能存在重复时段,实现int[][] merge(int[][] dateRangePrices)来修正结果。

  • 若平均价格相等,重复时段要被合并;
  • 若平均价格不相等,重复时段内的价格以后一时段为准。

如:

  • {10, 60, 250},{20, 50, 300}被修正为{10, 20, 250}、{20, 50, 300}和{50, 60, 250};
  • {10, 40, 250},{20, 50, 250}被修正为{10, 50, 250}。

可以参考合并重叠区间的解题思路。

定义时段类Range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package me.qunar;
import java.util.Comparator;
public class Range implements Comparator<Range> {
private int start;
private int end;
private int price;
public Range() {
}
public Range(int start, int end, int price) {
this.start = start;
this.end = end;
this.price = price;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
public int getPrice() {
return price;
}
// 时段比较器
public int compare(Range r1, Range r2) {
return r1.getStart() - r2.getStart();
}
}

Range类实现了java.util.Comparator接口,用于时间先后的比较。(Range类包含了平均价格price变量)

该题与合并重叠区间的不同之处在于:

  • 时间段是否合并不仅取决于时段是否重复,还取决于平均价格price(价格不同,不合并重复时段);

  • 由于重复时段的价格取决于后一时段,前一时段会按平均价格拆分。这里就需要由后至前分析时段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public int[][] merge(int[][] dateRangePrices) {
ArrayList<Range> list = new ArrayList<Range>();
// 价格以后一时段为准
// 定义list为ArrayList<Range>,方便引用时段
// 将dateRangePrices中的时段按逆序添加至list
for (int i = dateRangePrices.length - 1; i >= 0; i--) {
list.add(new Range(dateRangePrices[i][0], dateRangePrices[i][1], dateRangePrices[i][2]));
}
ArrayList<Range> result = new ArrayList<Range>();
// 将最后时段添加至result
result.add(list.get(0));
// 定义last为已知的最后时刻
int last = result.get(0).getEnd();
for (int i = 1; i < list.size(); i++) {
// 定义previous表示比较时的前一时段
// 定义next表示比较时的后一时段
Range previous = list.get(i);
Range next = result.get(result.size() - 1);
// 修正已知的最后时刻
if (previous.getEnd() > last) {
result.add(new Range(last, previous.getEnd(), previous.getPrice()));
last = previous.getEnd();
}
// 两时段存在重复区间
if (next.getStart() <= previous.getEnd()) {
// 两时段的价格相同,合并重复区间
if (next.getPrice() == previous.getPrice()) {
int start = Math.min(previous.getStart(), next.getStart());
// 前一步添加至result的时间段需要修正
result.remove(result.size() - 1);
previous = new Range(start, next.getEnd(), next.getPrice());
// 两时段的价格不同,以后一时段为准修正重复区间
} else {
int end = next.getStart();
previous = new Range(previous.getStart(), end, previous.getPrice());
}
}
// 两时段不存在重复区间,或重复区间已修正
result.add(previous);
}
// 重新按时序排列各时间段
Collections.sort(result, new Range());
int[][] array = new int[result.size()][3];
for (int i = 0; i < result.size(); i++) {
array[i][0] = result.get(i).getStart();
array[i][1] = result.get(i).getEnd();
array[i][2] = result.get(i).getPrice();
}
return array;
}

简单的测试程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
int[][] range = { { 10, 60, 250 },
{ 20, 50, 300 },
{ 40, 45, 350 },
{ 50, 55, 300 }
};
int[][] result = merge(range);
for (int i = 0; i < result.length; i++) {
System.out.println("[" + result[i][0] + ", " + result[i][1] + ", " + result[i][2] + "]");
}
}

输出结果为:

1
2
3
4
5
[10, 20, 250]
[20, 40, 300]
[40, 45, 350]
[50, 55, 300]
[55, 60, 250]