3
\$\begingroup\$

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

}
\$\endgroup\$
1
\$\begingroup\$
            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);
        }
\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I understand your concerns regarding shouldBeCalculatedCorrectlyWhen however you have not really came up with the alternate convention what you are suggesting. \$\endgroup\$ – Exploring Apr 9 '18 at 21:44
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.