BiggestOverlap.java

import java.util.Arrays;

public class BiggestOverlap {
    static class Interval {
        int start, end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    private static int calculateOverlap(Interval a, Interval b) {
        if (a.end < b.start || b.end < a.start) {
            return 0;
        }
        return Math.min(a.end, b.end) - Math.max(a.start, b.start) + 1;
    } 

    private static int findMaxIntervalOverlap(Interval[] intervals, int left, int right) {
        if (right - left <= 1) {
            return calculateOverlap(intervals[left], intervals[right]);
        }

        int mid = (left + right) / 2;

        int leftMax = findMaxIntervalOverlap(intervals, left, mid);
        int rightMax = findMaxIntervalOverlap(intervals, mid + 1, right);

        int crossMax = 0;
        for (int i = left; i <= mid; i++) {
            for (int j = mid + 1; j <= right; j++) {
                crossMax = Math.max(crossMax, calculateOverlap(intervals[i], intervals[j]));
            }
        }

        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    public static int getMaxOverlap(Interval[] intervals) {
        Arrays.sort(intervals, (a, b) -> a.start - b.start);
        return findMaxIntervalOverlap(intervals, 0, intervals.length - 1);
    }

    public static void main(String[] args) {
        Interval[] intervals = {
            new Interval(1, 7),
            new Interval(3, 9),
            new Interval(4, 8),
            new Interval(10, 12)
        };

        int maxOverlap = getMaxOverlap(intervals);
        System.out.println("The length of the biggest overlap is: " + maxOverlap);
    }
}