Merge intervals

Question

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

GitHub

public class MergingRanges {

    public static class Interval {
        int start;
        int end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public static Interval newInterval(int start, int end) {
            return new Interval(start, end);
        }

        @Override
        public int hashCode() {
            return Objects.hash(start, end);
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Interval) {
                Interval other = (Interval) o;
                return this.start == other.start && this.end == other.end;
            }

            return false;
        }

        public String toString() {
            return new StringBuilder("(start").append(start).append(",end=").append(end).append(")").toString();
        }
    }

    public static List<Interval> mergeRanges(List<Interval> intervals) {
        if (intervals.size() < 1) {
            throw new IllegalArgumentException();
        }

        intervals.sort(Comparator.comparingInt(o -> o.start));
        List<Interval> mergedIntervals = new ArrayList<>();

        Interval pastInterval = intervals.get(0);

        for (int i = 1; i < intervals.size(); i++) {
            Interval currentInterval = intervals.get(i);

            if (currentInterval.start <= pastInterval.end) {
                // if the past interval can be merged with the current interval
                if (currentInterval.end > pastInterval.end) {
                    // this means currentInterval finishes outside of the past-intervals limit
                    Interval newInterval = new Interval(pastInterval.start, currentInterval.end);
                    pastInterval = newInterval;
                }
            } else {
                // as the past interval cannot be merged within the current interval, its the beginning of new interval
                mergedIntervals.add(pastInterval);
                pastInterval = currentInterval;
            }
        }
        mergedIntervals.add(pastInterval);

        return mergedIntervals;
    }

}


public class MergingRangesTest {

    @Test
    public void shouldBeMergedWhenTheyJustTouchesTheBoundary() {
        //
        // [Meeting(1, 2), Meeting(2, 3)]
        // These meetings should be merged, although they don't exactly "overlap"—they just "touch."
        //
        List<Interval> mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(1, 2), newInterval(2, 3)));
        assertEquals(newInterval(1, 3), mergedIntervals.get(0));
    }

    @Test
    public void shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther() {
        //
        // Notice that although the second meeting starts later, it ends before the first meeting ends.
        // Does your method correctly handle the case where a later meeting is "subsumed by" an earlier meeting?
        //
        List<Interval> mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(1, 5), newInterval(2, 3)));
        assertEquals(newInterval(1, 5), mergedIntervals.get(0));

        // here (1,10) contains the rest of the interval, can we handle this?
        mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(1, 10), newInterval(2, 6), newInterval(3, 5), newInterval(7, 9)));
        assertEquals(newInterval(1, 10), mergedIntervals.get(0));
    }

    @Test
    public void mergeRanges() throws Exception {
        List<Interval> mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(0, 1), newInterval(3, 5), newInterval(4, 8), newInterval(10, 12), newInterval(9, 10)));

        //   [Meeting(0, 1), Meeting(3, 8), Meeting(9, 12)]
        assertEquals(newInterval(0, 1), mergedIntervals.get(0));
        assertEquals(newInterval(3, 8), mergedIntervals.get(1));
        assertEquals(newInterval(9, 12), mergedIntervals.get(2));
    }

}

Answer 1

            if (currentInterval.start <= pastInterval.end) {
                // if the past interval can be merged with the current interval
                if (currentInterval.end > pastInterval.end) {
                    // this means currentInterval finishes outside of the past-intervals limit
                    Interval newInterval = new Interval(pastInterval.start, currentInterval.end);
                    pastInterval = newInterval;
                }
            } else {
                // as the past interval cannot be merged within the current interval, its the beginning of new interval
                mergedIntervals.add(pastInterval);
                pastInterval = currentInterval;
            }

This is quite a minor nit-pick, but where nested ifs can be avoided it can make the code more readable:

        if (currentInterval.start > pastInterval.end) {
            // as the past interval cannot be merged within the current interval, its the beginning of new interval
            mergedIntervals.add(pastInterval);
            pastInterval = currentInterval;
        }
        else if (currentInterval.end > pastInterval.end) {
            // this means currentInterval finishes outside of the past-intervals limit
            Interval newInterval = new Interval(pastInterval.start, currentInterval.end);
            pastInterval = newInterval;
        }

Also, IMO newInterval is pointless, so I would make the further simplification of eliminating it to get:

        if (currentInterval.start > pastInterval.end) {
            // as the past interval cannot be merged within the current interval, its the beginning of new interval
            mergedIntervals.add(pastInterval);
            pastInterval = currentInterval;
        }
        else if (currentInterval.end > pastInterval.end) {
            // this means currentInterval finishes outside of the past-intervals limit
            pastInterval = new Interval(pastInterval.start, currentInterval.end);
        }

Answer 2

Some things:

• It seems the global structure could be easier understood by pulling out Interval as a top level class and then creating an IntervalList class (maybe as a child of List). IntervalList could then have a dummy constructor which takes nothing and creates an empty list plus an addInterval method which adds a single Interval to the list. This way as far as I can tell nothing has to be static and the merge code can be simpler.
• The toString method is redundant.
• shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther tests subsumption with both a single and multiple intervals. To me this is a hint that the refactoring suggestion at the top of this list will simplify things, since the second part of that test is pointless if the looping happens in the caller.
• mergeRanges tests various combinations of intervals, and like shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther should be redundant after a refactoring.
• In general, names like shouldBeCalculatedCorrectlyWhen… are not helpful. First, obviously you aren't going to test when things are calculated incorrectly, so it's a vacuous statement. Second, it's not the most precise statement you can make about what you expect it to do. From what I understand it seems the purpose is to verify that the original interval is returned when merged with a contained interval (pointing towards something like shouldReturnOriginalIntervalAfterMergingWithSubsumedInterval), alternatively that the List of Intervals is unchanged after merging with a contained interval (hinting at something like shouldNotChangeIntervalWhenMergedWithSubsumedInterval). I'm being deliberately vague here because it's very context dependent what the test should be called - the idea is to concisely give the reader as much information as possible about how the code should operate.
• Always test the entire result. The first test in shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther checks the first element of mergedIntervals, but it doesn't verify that that is the only element in there. It would be very easy for a bug to sneak in where there are more elements in the list than you are checking. In this case I would simply check equality of the entire mergedIntervals.

Answer 3

Interval class

• Such a simple data-holding class should be immutable, thus the fields should be private and have getter methods.

• The static construction method newInterval is a bit pointless. All that it saves is a single space compared with the constructor. If you want to use such a method, it's usually custom to call it of and use it exclusively by making the actual constructor private.

• In the equals method it would be good idea to compare the object references first:

  @Override
  public boolean equals(Object o) {
      if (this == o) {
          return true;
      }
      if (o instanceof Interval) {
          Interval other = (Interval) o;
          return this.start == other.start && this.end == other.end;
      }
  
      return false;
  }
  

• In the toString method, simply use string concatenation:

  "(start" + start + ",end=" + end + ")"

  It better readable and the compiler will make a StringBuilder out of it internally anyway.

mergeRanges method

• The method should have a signature as "wide" as possible. Since the order of the intervals isn't relevant, it would make sense to use Collection instead of List as the input and return parameters.

• The sort modifies the input list, something you should avoid, since the caller may not expect it. Better would be to create a sorted copy (which you'd have to do anyway, if you use a Collection as an input type). For this it would make sense to use a SortedSet have the Interval class implement Comparable:

---

public static class Interval implements Comparable<Interval> {

    // Requires the getters to be defined
    private static Comparator<Interval> NATURAL_ORDER_COMPARATOR = Comparator.comparingInt(Interval::getStart)
        .thenComparing(Interval::getEnd);


    // ...

    @Override
    public int compareTo(Housenumber other) {
      return NATURAL_ORDER_COMPARATOR.compare(this, other);
    }
}

---

• Merging to intervals seems to be a common operation, that could be useful outside of this algorithm, so I'd remove it and place it into the Interval class:

---

public Optional<Interval> merge(Interval other) {
  if (this.end > other.start || this.start < other.end) {
     return Optional.of(new Interval(Math.min(this.start, other.start)), Math.max(this.end, other.end));
  }
  return Optional.empty();
}

---

And the loop becomes:

---

for (int i = 1; i < intervals.size(); i++) {
        Interval currentInterval = intervals.get(i);

        Optional<Interval> newInterval = pastInterval.merge(currentInterval);
        if (newInterval.isPresent()) {
            pastInterval = newInterval.get();
        } else {
            mergedIntervals.add(pastInterval);
            pastInterval = currentInterval;
        }
    }
    mergedIntervals.add(pastInterval);
}

---

(This is not a nice use of Optional. If you don't like it, you can have the merge method just as well return null.)

(Also, all code is untested).