MergeIntervals.java

import java.util.ArrayList;
import java.util.List;

public class MergeIntervals {

    public List<Interval> merge(List<Interval> intervalListOne, List<Interval> intervalListTwo) {
        List<Interval> mergedIntervals = new ArrayList<>();
        int idxOne = 0;
        int idxTwo = 0;
        int currIntervalStart = -1;
        int currIntervalEnd = -1;
        while (idxOne < intervalListOne.size() || idxTwo < intervalListTwo.size()) {
            Interval nextInterval;
            if (idxOne == intervalListOne.size()) {
                nextInterval = intervalListTwo.get(idxTwo++);
            } else if (idxTwo == intervalListTwo.size()) {
                nextInterval = intervalListOne.get(idxOne++);
            } else {
                Interval firstInterval = intervalListOne.get(idxOne);
                Interval secondInterval = intervalListTwo.get(idxTwo);
                if (firstInterval.start < secondInterval.start) {
                    nextInterval = firstInterval;
                    idxOne++;
                } else {
                    nextInterval = secondInterval;
                    idxTwo++;
                }
            }
            if (currIntervalStart == -1) {
                currIntervalStart = nextInterval.start();
                currIntervalEnd = nextInterval.end();
            } else if (currIntervalEnd >= nextInterval.start) {
                currIntervalEnd = Math.max(currIntervalEnd, nextInterval.end);
            } else {
                mergedIntervals.add(new Interval(currIntervalStart, currIntervalEnd));
                currIntervalStart = nextInterval.start();
                currIntervalEnd = nextInterval.end();
            }
        }
        if (currIntervalStart != -1) {
            mergedIntervals.add(new Interval(currIntervalStart, currIntervalEnd));
        }
        return mergedIntervals;
    }

    public record Interval(int start, int end) {}
}


// TESTS
import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;


import static org.junit.Assert.assertEquals;

public class MergeIntervalsTest {

    private MergeIntervals mergeIntervals;

    @Before
    public void setUp() {
        mergeIntervals = new MergeIntervals();
    }

    @Test
    public void mergeSuccess() {
        // Arrange
        List<MergeIntervals.Interval> intervalOne = Arrays.asList(
                new MergeIntervals.Interval(1, 4),
                new MergeIntervals.Interval(5, 9)
        );
        List<MergeIntervals.Interval> intervalTwo = Arrays.asList(
                new MergeIntervals.Interval(2, 3),
                new MergeIntervals.Interval(3, 5)
        );

        // Act
        List<MergeIntervals.Interval> result = mergeIntervals.merge(intervalOne, intervalTwo);

        // Assert
        assertEquals(1, result.size());
        assertEquals(1, result.get(0).start());
        assertEquals(9, result.get(0).end());
    }

    @Test
    public void overlappingIntervalsAcrossList() {
        // Arrange
        List<MergeIntervals.Interval> intervalOne = Arrays.asList(
                new MergeIntervals.Interval(1, 4),
                new MergeIntervals.Interval(7, 10),
                new MergeIntervals.Interval(12, 15)
        );
        List<MergeIntervals.Interval> intervalTwo = Arrays.asList(
                new MergeIntervals.Interval(2, 6),
                new MergeIntervals.Interval(8, 11)
        );

        // Act
        List<MergeIntervals.Interval> result = mergeIntervals.merge(intervalOne, intervalTwo);

        // Assert
        assertEquals(3, result.size());
        assertEquals(new MergeIntervals.Interval(1, 6), result.get(0));
        assertEquals(new MergeIntervals.Interval(7, 11), result.get(1));
        assertEquals(new MergeIntervals.Interval(12, 15), result.get(2));
    }

    @Test
    public void overlappingIntervalsMultipleMergeAcrossList() {
        // Arrange
        List<MergeIntervals.Interval> intervalOne = Arrays.asList(
                new MergeIntervals.Interval(1, 3),
                new MergeIntervals.Interval(5, 7),
                new MergeIntervals.Interval(9, 11)
        );
        List<MergeIntervals.Interval> intervalTwo = Arrays.asList(
                new MergeIntervals.Interval(2, 4),
                new MergeIntervals.Interval(6, 8),
                new MergeIntervals.Interval(10, 12)
        );

        // Act
        List<MergeIntervals.Interval> result = mergeIntervals.merge(intervalOne, intervalTwo);

        // Assert
        assertEquals(3, result.size());
        assertEquals(new MergeIntervals.Interval(1, 4), result.get(0));
        assertEquals(new MergeIntervals.Interval(5, 8), result.get(1));
        assertEquals(new MergeIntervals.Interval(9, 12), result.get(2));
    }

    @Test
    public void nonOverlappingIntervals() {
        // Arrange
        List<MergeIntervals.Interval> intervalOne = Arrays.asList(
                new MergeIntervals.Interval(1, 3),
                new MergeIntervals.Interval(5, 7),
                new MergeIntervals.Interval(9, 11)
        );
        List<MergeIntervals.Interval> intervalTwo = Arrays.asList(
                new MergeIntervals.Interval(12, 15),
                new MergeIntervals.Interval(16, 20)
        );

        // Act
        List<MergeIntervals.Interval> result = mergeIntervals.merge(intervalOne, intervalTwo);

        // Assert
        assertEquals(5, result.size());
        assertEquals(new MergeIntervals.Interval(1, 3), result.get(0));
        assertEquals(new MergeIntervals.Interval(5, 7), result.get(1));
        assertEquals(new MergeIntervals.Interval(9, 11), result.get(2));
        assertEquals(new MergeIntervals.Interval(12, 15), result.get(3));
        assertEquals(new MergeIntervals.Interval(16, 20), result.get(4));
    }

    @Test
    public void overlappingIntervalsWithMergesAndGaps() {
        // Arrange
        List<MergeIntervals.Interval> intervalOne = Arrays.asList(
                new MergeIntervals.Interval(1, 5),
                new MergeIntervals.Interval(7, 10)
        );
        List<MergeIntervals.Interval> intervalTwo = Arrays.asList(
                new MergeIntervals.Interval(2, 3),
                new MergeIntervals.Interval(4, 6),
                new MergeIntervals.Interval(8, 12)
        );

        // Act
        List<MergeIntervals.Interval> result = mergeIntervals.merge(intervalOne, intervalTwo);

        // Assert
        assertEquals(2, result.size());
        assertEquals(new MergeIntervals.Interval(1, 6), result.get(0));
        assertEquals(new MergeIntervals.Interval(7, 12), result.get(1));
    }
}