基于端点递归加入间隔列表

Question

我有三个区间：

10:00上午 - 11:00AM

11:00AM - 11:30AM

和3:00PM - 3:30PM

我已经编写了这个算法来递归地压缩和合并间隔，如果它们重叠或共享端点。

 public boolean optimizeIntervals(ArrayList<Interval> list) {
    ArrayList<Interval> listToOptimize = list;
    ArrayList<Interval> optimizedList = new ArrayList<Interval>();
    for (int i = 1; i < listToOptimize.size(); i++) {
        if (listToOptimize.get(i).getStart().equals(listToOptimize.get(i - 1).getEnd())) {
            optimizedList.add(new Interval(listToOptimize.get(i - 1).getStart(), listToOptimize.get(i).getEnd()));
        }else{
            optimizedList.add(new Interval(listToOptimize.get(i).getStart(), listToOptimize.get(i).getEnd()));
        }
    }
    if(optimizedList.size() == listToOptimize.size()){
        setMeetingDuringIntervals(optimizedList);
        return true;
    }else{
        optimizeIntervals(optimizedList);
    }

    return false;
}

然而，在使用调试器跟踪堆栈跟踪后，我注意到当第一次递归调用后列表的大小为 2 时，我丢失了 3:00PM 的最终 Interval - 3:30PM

如何重写该算法以不丢失我的最终值？\

我的问题是这样的：

运行 1

加入间隔 1 和 2

创建 10:00 AM - 11:30 AM

不使用 3:00PM - 3:30PM

递归调用

检查 3:00-3:30PM 是否与间隔 1 有任何重叠？

没有

只添加3:00-3:30PM

我的代码逻辑：

如果 i 的 start time 匹配 i-1 的 end time。将它们添加到优化列表中。

如果没有，

仅将 i 添加到优化列表。

然而，在当前的解决方案中，算法在第二个运行上搞砸了，从 i 从 1 开始，只添加了 3:00 - 3:30 下午而不是第一个间隔？

Answer 1

所以我用这个算法解决了我的问题：

  public boolean optimizeIntervals(ArrayList<Interval> list) {
    ArrayList<Interval> listToOptimize = list;
    ArrayList<Interval> optimizedList = new ArrayList<Interval>();
    for (int i = 1; i < listToOptimize.size(); i++) {
        if(listToOptimize.size()==2){
            if (listToOptimize.get(i).getStart().equals(listToOptimize.get(i - 1).getEnd())) {
                optimizedList.add(new Interval(listToOptimize.get(i - 1).getStart(), listToOptimize.get(i).getEnd()));
            }else if(listToOptimize.get(i).getStart().isAfter(listToOptimize.get(i-1).getEnd())){
                optimizedList.add(new Interval(listToOptimize.get(i).getStart(), listToOptimize.get(i).getEnd()));
                optimizedList.add(new Interval(listToOptimize.get(i-1).getStart(), listToOptimize.get(i-1).getEnd()));
            }
        }
        else{
             if (listToOptimize.get(i).getStart().equals(listToOptimize.get(i - 1).getEnd())) {
                optimizedList.add(new Interval(listToOptimize.get(i - 1).getStart(), listToOptimize.get(i).getEnd()));
            } else if (listToOptimize.get(i).getStart().isAfter(listToOptimize.get(i - 1).getEnd())) {
                optimizedList.add(new Interval(listToOptimize.get(i).getStart(), listToOptimize.get(i).getEnd()));
            }
        }
    }
    if(optimizedList.size() == listToOptimize.size()){
        setMeetingDuringIntervals(optimizedList);
        return true;
    }else{
        optimizeIntervals(optimizedList);
    }

    return false;
}

如果存在最终连接（意味着列表大小为 2），则处理这种情况；

我不知道是否有更好的方法来处理这个问题，但它确实有效。

Answer 2

function compress(list) {
  if(list.length < 2) { return list; }
  // sort your interval list by the first value
  var sortedList = list.sort(function(a, b) { return a[0] - b[0]; });
  // compress your list into an result set
  var result = [sortedList[0]];
  var working = result[0];
  for(var i = 1; i < sortedList.length; i++) {
    var current = sortedList[i];
    // does the first value overlap the range?
    if(current[0] >= working[0] && current[0] <= working[1]) {
      // update the second value of the range
      working[1] = Math.max(current[1], working[1]);
    } else {
      // add a new unique range
      result.push(current);
      working = result[result.length - 1];
    }
  }
  return result;
}

var intervals = [[1,3], [3,5], [6,10], [11,13], [13,14]];
console.log(JSON.stringify(compress(intervals)));

基于端点递归加入间隔列表

Recursively Joining Lists of Intervals based on endpoints

algorithm

jodatime

intervals