Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Merge overlapping intervals challenge

Sharing is caring!

Problem statement
Given a set of intervals in any order merge the overlapping intervals and return the list of merged intervals.

Sample input

[{6,8} {2,4} {1,3} {5,5} {-1,4} {3,4} {6,8} {8,10}]

Sample output

[{-1,4} {5,5} {6,10}]

Solution
The first step we are going to take is sort the intervals in ascending order based on their ending time.

Next, we are going to traverse over the sorted list and as long as two adjacent intervals interval_1 and interval_2 overlap (interval_2.start \le interval_1.end) we keep merging them by taking min(interval_1.start, interval_2.start) as the new start and interval_2.end as the new end for our new interval.

Once no more adjacent intervals are merging we add the newly created interval to our new list and resume the traversal until we have visited all intervals in the original list.

Full code

public class MergeIntervals {
    private static List merge(List intervals) {
        List ans = new ArrayList<>();

        // Sort in ASC order depending on their ending time.
        Collections.sort(intervals, new Comparator() {

            /**
             * This method returns zero if the objects are equal.
             * It returns a positive value if interval1 is greater than interval2.
             * Otherwise, a negative value is returned.
             */
            @Override
            public int compare(Integer[] interval1, Integer[] interval2) {
                return interval1[1] - interval2[1];
            }
        });


        int n = intervals.size();
        Integer[] cur = intervals.get(0);
        int i = 1;
        while (i < n) {
            Integer[] next = intervals.get(i);
            while (next[0] <= cur[1] && i < intervals.size()) {
                cur[0] = Math.min(cur[0], next[0]);
                cur[1] = next[1];

                i++;
                if (i < intervals.size()) {
                    next = intervals.get(i);
                }

            }

            ans.add(cur);
            cur = next;
        }


        return ans;
    }


    public static void main(String[] args) throws FileNotFoundException {
        List intervals = new ArrayList<>();
        intervals.add(new Integer[]{6, 8});
        intervals.add(new Integer[]{2, 4});
        intervals.add(new Integer[]{1, 3});
        intervals.add(new Integer[]{5, 5});
        intervals.add(new Integer[]{-1, 4});
        intervals.add(new Integer[]{3, 4});
        intervals.add(new Integer[]{6, 8});
        intervals.add(new Integer[]{8, 10});

        System.out.println("Not merged:");
        for (Integer[] interval : intervals) {
            System.out.print("{" + interval[0] + "," + interval[1] + "} ");
        }


        List result = merge(intervals);

        System.out.println("\n\nMerged:");
        for (Integer[] interval : result) {
            System.out.print("{" + interval[0] + "," + interval[1] + "} ");
        }

    }
}