Understanding the Problem

Given a collection of intervals represented as an array of pairs [start, end], the task is to merge overlapping intervals and return a new array of non-overlapping intervals.

Approach

To merge intervals efficiently, we can follow these steps:

1. Create a class Interval to represent each interval with start and end attributes.
2. Implement the Comparable interface in the Interval class to compare intervals based on their start values. If two intervals have the same start value, compare them based on their end values in descending order.
3. Sort the array of intervals based on their start values using Collections.sort().
4. Iterate through the sorted intervals and merge overlapping intervals.

Java Implementation

Let’s implement the above approach in Java:

import java.util.*;

class Interval implements Comparable<Interval> {
    int start, end;

    Interval(int s, int e) {
        start = s;
        end = e;
    }

    public int compareTo(Interval other) {
        int p = Integer.compare(this.start, other.start);
        if (p != 0) return p;
        return -1 * Integer.compare(this.end, other.end);
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        ArrayList<Interval> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            list.add(new Interval(intervals[i][0], intervals[i][1]));
        }
        Collections.sort(list);

        ArrayList<Interval> mergedIntervals = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            if (mergedIntervals.isEmpty()) {
                mergedIntervals.add(list.get(i));
            } else {
                Interval prev = mergedIntervals.get(mergedIntervals.size() - 1);
                Interval current = list.get(i);
                if (current.start >= prev.start && current.start <= prev.end) {
                    prev.end = Math.max(current.end, prev.end);
                } else {
                    mergedIntervals.add(current);
                }
            }
        }

        int[][] result = new int[mergedIntervals.size()][2];
        for (int i = 0; i < mergedIntervals.size(); i++) {
            result[i][0] = mergedIntervals.get(i).start;
            result[i][1] = mergedIntervals.get(i).end;
        }
        return result;
    }
}

Conclusion

In this blog, we discussed how to merge overlapping intervals efficiently using Java. By implementing the Comparable interface and following the described approach, we can solve the problem of merging intervals effectively.