Merge Overlapping Intervals in a Java Collection

1. Overview

In this tutorial, we’ll look at taking a Collection of intervals and merging any that overlap.

2. Understanding the Problem

First, let’s define what an interval is. We’ll describe it as a pair of numbers where the second is greater than the first. This could also be dates, but we’ll stick with integers here. So for example, an interval could be 2 -> 7, or 100 -> 200.

We can create a simple Java class to represent an interval. We’ll have start as our first number and end as our second and higher number:

class Interval {
    int start;
    int end;

    // Usual constructor, getters, setters and equals functions

}

Now, we want to take a Collection of Intervals and merge any that overlap. We can define overlapping intervals as anywhere the first interval ends after the second interval starts. For example, if we take two intervals 2 -> 10 and 5 -> 15 we can see that they overlap and the result of merging them would be 2 -> 15.

3. Algorithm

To perform the merge, we’ll need code following this pattern:

List<Interval> doMerge(List<Interval> intervals) {
    intervals.sort(Comparator.comparingInt(interval -> interval.start));
    ArrayList<Interval> merged = new ArrayList<>();
    merged.add(intervals.get(0));
 
    // < code to merge intervals into merged comes here >
 
    return merged;
}

To start, we’ve defined a method that takes a List of Intervals and returns the same but sorted. Of course, there are other types of Collections our Intervals could be stored in, but we’ll use a List today.

The first step in processing is sorting our Collection of intervals. We’ve sorted based on the Interval’s start so that when we loop over them, each Interval is followed by the one most likely to overlap with it. 

We can use List.sort() to do this assuming our Collection is a List. However, if we had a different kind of Collection we’d have to use something else. List.sort() takes a Comparator and sorts in place, so we don’t need to reassign our variable. We employed Comparator.comparingInt() as the Comparator for the sort() method.

Next, we need somewhere to put the results of our merging process. We’ve created an ArrayList called merged for this purpose. We can also get it started by putting in the first interval as we know it has the earliest start.

Now, we’ll merge intervals‘ elements into merged, which the major part of the solution. Depending on an interval‘s start and end, there are three possibilities. Let’s draw an ASCII chart to help us understand the merge logic more easily:

-----------------------------------------------------------------------
| Legend:                                                             |
| |______|  <-- lastMerged - The last lastMerged interval             |
|                                                                     |
| |......|  <-- interval - The next interval in the sorted input list |
-----------------------------------------------------------------------


## Case 1: interval.start <= lastMerged.end && interval.end > lastMerged.end

 lastMerged.start         lastMerged.end
  |______________________________|

         |...............................|
     interval.start        interval.end


## Case 2: interval.start <= lastMerged.end && interval.end <= lastMerged.end 

 lastMerged.start         lastMerged.end
  |______________________________|

      |..................|
  interval.start     interval.end


## Case 3: interval.start > lastMerged.end 

 lastMerged.start         lastMerged.end
  |_________________________|

                               |..............|
                     interval.start        interval.end

According to the ASCII chart, we have detected overlapping in case 1 and case 2. To resolve this, we need to merge the lastMerged and the interval. Fortunately, merging them is a straightforward process. We can update lastMerged.end by choosing the greater value between lastMerged.end and interval.end:

if (interval.start <= lastMerged.end){
    lastMerged.setEnd(max(interval.end, lastMerged.end));
}

In case 3, there is no overlapping, so we add the current interval as a new element to the result list merged:

merged.add(interval);

Finally, let’s get the complete solution by adding the merge logic implementation to the doMerge() method:

List<Interval> doMerge(List<Interval> intervals) {
    intervals.sort(Comparator.comparingInt(interval -> interval.start));
    ArrayList<Interval> merged = new ArrayList<>();
    merged.add(intervals.get(0));
 
    intervals.forEach(interval -> {
        Interval lastMerged = merged.get(merged.size() - 1);
        if (interval.start <= lastMerged.end){
            lastMerged.setEnd(max(interval.end, lastMerged.end));
        } else {
            merged.add(interval);
        }
    });
 
    return merged;
}

4. Practical Example

Let’s see that method in action with a test. We can define some Intervals we want to merge:

List<Interval> intervals = new ArrayList<>(Arrays.asList(
    new Interval(3, 5),
    new Interval(13, 20),
    new Interval(11, 15),
    new Interval(15, 16),
    new Interval(1, 3),
    new Interval(4, 5),
    new Interval(16, 17)
));

After merging, we’d expect the result to be only two Intervals:

List<Interval> intervalsMerged = new ArrayList<>(Arrays.asList(
    new Interval(1, 5), 
    new Interval(11, 20)
));

We can now use the method we created earlier and confirm it works as expected:

MergeOverlappingIntervals merger = new MergeOverlappingIntervals();
List<Interval> result =  merger.doMerge(intervals);
assertEquals(intervalsMerged, result);

5. Conclusion

In this article, we learned how to merge overlapping intervals in a Collection in Java. We saw that the process of merging the intervals is fairly simple. First, we must know how to properly sort them, by start value. Then, we just have to understand that we need to merge them when one interval starts before the previous one ends.