予有间隔与整数值[例如列表。 [1,4],[10,19]等]。有没有一种方法把这些间隔成一些Java集合容器[如。设置],这样我可以调用容器上的联盟的功能。该联盟的功能应该给我时间间隔,这样如果有2插入间隔重叠那么就应该在输出合并的列表。 我试着用番石榴的范围类,但最终合并前相比对对方的所有时段。优雅的方法,这将是真正的AP preciated!这是基于以下的反应是什么我都试过了。的输出为[[1,15],[17,20]],这是正确的。我想知道是否有一些退出的API,实现了这样的事情。
I have a list of intervals with integer values [eg. [1, 4], [10, 19] etc.]. Is there a way to put these intervals into some java collections' container [eg. Set] such that I can call a 'union' function on the container. The 'union' function should give me a list of intervals such that if any 2 inserted intervals overlap then they should be merged in the output. I tried using the Range class in Guava but ended up comparing all the intervals against each other before merging. An elegant approach to this would be really appreciated ! Here is what I have tried based on the response below. The output is [[1, 15], [17, 20]], which is correct. I wanted to know if there is some exiting API which implements something like this.
public static void main(String[] args) {
// mock data
List<MyIntRange> rng_lst = new ArrayList<Junk.MyIntRange>();
rng_lst.add(new MyIntRange(1, 10));
rng_lst.add(new MyIntRange(5, 15));
rng_lst.add(new MyIntRange(17, 20));
// sort intervals by start position
Collections.sort(rng_lst);
// merge the intervals which overlap
List<MyIntRange> res_lst = new ArrayList<Junk.MyIntRange>();
MyIntRange old_rng = null;
for (MyIntRange cur_rng : rng_lst) {
if (old_rng == null) {
old_rng = cur_rng;
} else {
if (old_rng.rng.upperEndpoint() < cur_rng.rng.lowerEndpoint()) {
// this does not over lap with the next one
res_lst.add(old_rng);
old_rng = cur_rng;
} else {
// overlap
old_rng = new MyIntRange(old_rng.rng.lowerEndpoint(),
cur_rng.rng.upperEndpoint());
}
}
}
// add the last range
res_lst.add(old_rng);
// done!
System.out.println(res_lst);
}
// wrapper around Guava's Range to make it comparable based on the
// interval's start
public static class MyIntRange implements Comparable<MyIntRange> {
Range<Integer> rng;
public MyIntRange(int start, int end) {
rng = Ranges.closed(start, end);
}
public int compareTo(MyIntRange that) {
int res = -1;
if (this.rng.lowerEndpoint() > that.rng.lowerEndpoint()) {
res = 1;
}
return res;
}
public String toString() {
return "[" + rng.lowerEndpoint() + ", " + rng.upperEndpoint() + "]";
}
}
感谢
这基本上是什么 RangeSet
确实在刚刚发布的番石榴14.0,但它的合并你,而不是告诉你哪些范围可以合并。
This is basically exactly what RangeSet
does in the just-released Guava 14.0, except it does the merging for you, rather than telling you which ranges could be merged.