在一个循环中合并区间

huangapple go评论81阅读模式
英文:

Merge intervals in one for-loop

问题

这可能是一个奇怪的问题,但我正在尝试合并区间时间,并且只是困扰于循环外有一行代码 - 我真的想将那行代码(哈哈。)合并到循环中,并且希望一切都一次性发生。

问题:举个例子,假设给定区间为(1, 5)、(3, 7)、(4, 6)、(6, 8)、(10, 12)、(12, 15),程序应返回(1, 8)、(10, 15),因为这些区间合并了所有重叠的部分。

我的方法是,我有一个当前值,带有第一对的值,然后我从1到末尾运行一个for循环,检查我当前所在的Pair是否与我的当前Pair合并。如果它合并了,我就更新当前Pair中的值;如果它没有合并,我就将当前Pair添加到结果列表中,然后将其值更新为我当前所在的节点。

请随意根据需要更改代码,以便在一个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>();
 
  //检查大小和空值
  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++) {

    //想要合并
    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;
    }
  }
  //循环在能够合并之前中断
  result.add(new Pair(current.first, current.second));

  return result;
  }
}
英文:

This might be a strange question but I'm trying to merge interval times and am just bothered that there's one line outside of the for-loop -- I really want to merge that line (haha.) into the for-loop and have everything happen at once.

Problem: Say for example you're given the Intervals (1, 5), (3, 7), (4, 6), (6, 8), (10, 12), (12, 15) the program should return (1,8),(10,15) as these merge all overlapping intervals.

My approach is that I have a current value with the values of the first pair, I then run a for-loop from 1 to the end and check if the Pair that I'm on merges with my current or not. If it does merge I update the values in my current pair and if it doesn't merge then I add current to my result list and then update its values to whatever node I'm currently on.

Feel free to change up the code however necessary to make it all work in one for-loop.
If you see any other errors with the code, please let me know. Thank you!

class Pair{
public int first;
public int second;
public Pair(int x, int y){
this.first = x;
this.second = y; 
}
}
class MergeIntervals{
static ArrayList&lt;Pair&gt; mergeIntervals(ArrayList&lt;Pair&gt; v) {
ArrayList&lt;Pair&gt; result = new ArrayList&lt;Pair&gt;();
//check for size &amp; 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 &lt; v.size(); i++) {
//want to merge
if(v.get(i).first &lt; current.second) {
if(v.get(i).second &gt; 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;
}
}

答案1

得分: 1

要总结对现有代码的可能更改/增强如下:

  • 在类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;
        }
        // 提前返回空列表或仅包含单个配对的情况
        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)]
英文:

To summarize possible changes/enhancements to the existing code:

  • in class Pair provide a copy constructor and override toString() for convenience
  • enhance verification of the input data in merge method
  • sort the input data to guarantee order of the intervals
  • use Pair copy constructor in the merge method
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 &quot;(&quot; + first + &quot;, &quot; + second + &quot;)&quot;;
    }
}

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

        return result;
    }
}

Test:

List&lt;Pair&gt; 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));

Output:

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

huangapple
  • 本文由 发表于 2020年10月23日 05:04:18
  • 转载请务必保留本文链接:https://go.coder-hub.com/64490532.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定