在java中设置的时间间隔

我有一个带整数值的间隔列表[例如。 [1,4]，[10，19]等]。有没有办法将这些间隔放入一些Java集合的容器中[例如。设置]，这样我就可以在容器上调用'联合'功能。 '联合'功能应该给我一个间隔列表，如果任何2个插入的间隔重叠，那么它们应该被合并到输出中。我尝试使用Guava中的Range类，但最终在合并之前比较了所有间隔。一个优雅的方法，将非常感激！以下是我根据下面的回复尝试过的内容。输出是[[1,15]，[17,20]]，这是正确的。我想知道是否有一些现有的API实现了这样的事情。在java中设置的时间间隔

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() + "]"; 
    } 
}

感谢

来源

2013-03-01 user1998031

是的，有一种方法可以做你想要做的事情。 [你有什么尝试？]（http://whathaveyoutried.com） – 2013-03-01 02:05:19

@ user1998031如果[9,13]和[10,15]那么你期待的结果是什么？ – 2013-03-01 02:11:42

与[此问题]类似（http://stackoverflow.com/questions/4648261/is-there-an-indexset-and-a-range-class-for-java）？ – prunge 2013-03-01 02:18:19

这基本上就是RangeSet在刚刚发布的番石榴14.0中所做的，除非它为您合并，而不是告诉您哪些范围可以合并。

来源

2013-03-01 02:33:29

这正是我一直在寻找的！ Guava中是否存在相应的RangeTree类，它实现了间隔树来回答问题，例如找到间隔CLOSEST到一个点或间隔？ – user1998031 2013-03-01 02:42:39

不，没有。尽管如此，你可以通过查看'subRangeSet'的'span'从'RangeSet'派生它。 – 2013-03-01 05:03:11

基本算法：

排序间隔由开始索引
漫步列表。对于i th项：
1. 比较i的结束索引与(i+1)项的开始索引。
2. 如果结束索引较大，请将结束索引i设置为结束索引i+1，并删除i+1元素。（此将它们合并。）

时间复杂度：O(nlgn)，因为最初的那种。（也就是说，如果清除是正确的）。

来源

2013-03-01 02:17:06 apnorton

更新了此算法的代码 – user1998031 2013-03-01 02:38:26

在java中设置的时间间隔

回答

相关问题