在一个 for 循环中合并区间

Question

这可能是一个奇怪的问题，但我正在尝试合并间隔时间，只是对 for 循环之外的一行感到困扰——我真的很想将该行合并（哈哈）到 for -循环并让所有事情立即发生。

问题：例如假设给定区间 (1, 5), (3, 7), (4, 6), (6, 8), (10, 12), (12, 15 ) 程序应该 return (1,8),(10,15) 因为这些合并所有重叠间隔。

我的方法是我有一个当前值和第一对的值，然后我运行从 1 到结束的 for 循环并检查我正在使用的对是否与合并我的当前与否。如果确实合并，我更新我当前对中的值，如果它不合并，那么我将当前添加到我的结果列表，然后将其值更新到我当前所在的任何节点。

请随意更改代码，但需要使它在一个 for 循环中全部工作。如果您发现代码有任何其他错误，请告诉我。谢谢！

class Pair{
    public int first;
    public int second;
    
    public Pair(int x, int y){
      this.first = x;
      this.second = y; 
    }
}

class MergeIntervals{
  static ArrayList<Pair> mergeIntervals(ArrayList<Pair> v) {
  ArrayList<Pair> result = new ArrayList<Pair>();
 
  //check for size & null
  if(v == null || v.size() == 0) {
    return null;
  } 
  if(v.size() == 0) {
    result.add(v.get(0));
    return result;
  }

  Pair current = new Pair(v.get(0).first, v.get(0).second);

  for(int i = 1; i < v.size(); i++) {

    //want to merge
    if(v.get(i).first < current.second) {
      if(v.get(i).second > current.second) {
        current.second = v.get(i).second;
      }
    }
    else {
      result.add(new Pair(current.first, current.second));
      current.first = v.get(i).first;
      current.second = v.get(i).second;
    }
  }
  //loop broke before was able to merge
  result.add(new Pair(current.first, current.second));

  return result;
  }
}

Answer 1

总结可能changes/enhancements到现有代码：

在 class Pair 中提供复制构造函数并为方便起见覆盖 toString()
增强merge方法中输入数据的验证
对输入数据进行排序以保证间隔的顺序
在merge方法中使用Pair复制构造函数

class Pair{
    public int first;
    public int second;
    
    public Pair(int x, int y){
        this.first = x;
        this.second = y; 
    }
    
    public Pair(Pair p) {
        this(p.first, p.second);
    }
    
    @Override
    public String toString() {
        return "(" + first + ", " + second + ")";
    }
}

class MergeIntervals{
    public static List<Pair> merge(List<Pair> v) {
        if (null == v) {
            return null;
        }
        // early return an empty list or containing a single pair
        if (v.size() < 1) {
            return v;
        }
        List<Pair> result = new ArrayList<>();
        
        Collections.sort(v, (a, b) -> Integer.compare(a.first, b.first));
        
        Pair current = new Pair(v.get(0));
        
        for (int i = 1; i < v.size(); i++) {
            Pair p = v.get(i);
            if (p.first <= current.second) {
                current.second = Math.max(p.second, current.second);
            } else {
                result.add(current);
                current = new Pair(p);
            }
        }
        result.add(current);

        return result;
    }
}

测试：

List<Pair> data = Arrays.asList(
    new Pair(3, 7),
    new Pair(1, 5),
    new Pair(6, 8),
    new Pair(4, 6),
    new Pair(10, 12),
    new Pair(12, 15)
);

System.out.println(MergeIntervals.merge(data));

输出：

[(1, 8), (10, 15)]

在一个 for 循环中合并区间

Merge intervals in one for-loop

java

algorithm

merge

arraylist

array-merge