# 56. Merge Intervals

## 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++) {
}
Collections.sort(list);

ArrayList<Interval> mergedIntervals = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
if (mergedIntervals.isEmpty()) {
} 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 {
}
}
}

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.