Posts Overlapping Intervals (geeksforgeeks - SDE Sheet)
Post
Cancel

Overlapping Intervals (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given a collection of Intervals, the task is to merge all of the overlapping Intervals.

geeksforgeeks

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution
{
    // Method to merge all overlapping intervals
    public int[][] overlappedInterval(int[][] intervals)
    {
        int n = intervals.length;

        // Sort intervals based on the starting point, and if they have the same start, sort by the ending point
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        // List to hold merged intervals
        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]); // Add the first interval to the list

        // The previous interval for comparison
        // We could have also used the list directly
        int[] prevInterval = intervals[0];

        // Iterate through all intervals
        for(int i = 1; i < n; i++){

            // Get the current interval
            int[] current = intervals[i];

            // If current interval does not overlap with the previous interval
            if(current[0] > prevInterval[1]){

                list.add(current); // Add the current interval to the list
                prevInterval = current; // Update previous interval

            } else {

                // Merge the current interval with the previous interval
                prevInterval[1] = Math.max(prevInterval[1], current[1]);

            }
        }

        // Convert the list of merged intervals to a 2D array
        int[][] res = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);

        return res;
    }
}
This post is licensed under CC BY 4.0 by the author.