Merge All Overlapping Intervals

package org.wesome.dsalgo;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.Arrays;
import java.util.Comparator;

@Data
@AllArgsConstructor
class Interval {
    int start, end;
}

public class OverlappingIntervals {
    public static void mergeIntervals(Interval arr[]) {
        /*  sort the array in ascending order based on start time    */
        Arrays.sort(arr, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });
        System.out.println("Array sorted on start time is = " + Arrays.toString(arr));
        int index = 0;
        for (int i = 1; i < arr.length; i++) {
            /*  check end of previous interval doesn't overlap with start of current interval   */
            if (arr[index].end >= arr[i].start) {
                /*  end of previous interval overlap with start of current interval, so merge privious and current interval   */
                arr[index].end = Math.max(arr[index].end, arr[i].end);
            } else {
                index++;
                arr[index] = arr[i];
            }
        }
        for (int i = 0; i <= index; i++) {
            System.out.print("[" + arr[i].start + "," + arr[i].end + "]");
        }
    }
}
package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

import static org.wesome.dsalgo.OverlappingIntervals.mergeIntervals;

public class OverlappingIntervalsTest {
    @Test
    void mergeIntervalsTest1() {
        Interval arr[] = new Interval[4];
        arr[0] = new Interval(6, 8);
        arr[1] = new Interval(1, 2);
        arr[2] = new Interval(2, 3);
        arr[3] = new Interval(4, 7);
        mergeIntervals(arr);
    }

    @Test
    void mergeIntervalsTest2() {
        Interval arr[] = new Interval[4];
        arr[0] = new Interval(6, 8);
        arr[1] = new Interval(1, 2);
        arr[2] = new Interval(2, 4);
        arr[3] = new Interval(4, 7);
        mergeIntervals(arr);
    }
}
plugins {
    id 'java'
    id "io.freefair.lombok" version "6.2.0"
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}

 

follow us on