Merge intervals in one for-loop

Question

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<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

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

Test:

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));

Output:

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