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()
}