Untitled

import java.util.*;

public class MinimumConnectedSets {

    public static void main(String[] args) {
             List<Integer> a = Arrays.asList(3, 2, 3);
         List<Integer> b = Arrays.asList(5,9,3);
        int k = 10;

        int result = minimumDivision(a, b, k);
        System.out.println("Minimum connected sets: " + result); // Expected output: 2
    }

    public static int minimumDivision(List<Integer> a, List<Integer> b, int k) {
        int n = a.size();
        List<int[]> intervals = new ArrayList<>();

        // Combine a and b into intervals
        for (int i = 0; i < n; i++) {
            intervals.add(new int[]{a.get(i), b.get(i)});
        }

        // Sort intervals by the start value
        intervals.sort(Comparator.comparingInt(interval -> interval[0]));

        int originalConnectedSets = countConnectedSets(intervals);
        int minConnectedSets = originalConnectedSets;

        // Try inserting the segment between every possible pair of intervals
        for (int i = 0; i <= n; i++) {
            int[] newInterval;

            if (i == 0) {
                // Insert segment before the first interval
                newInterval = new int[]{intervals.get(0)[0] - k, intervals.get(0)[0]};
            } else if (i == n) {
                // Insert segment after the last interval
                newInterval = new int[]{intervals.get(n - 1)[1], intervals.get(n - 1)[1] + k};
            } else {
                // Insert segment between intervals[i-1] and intervals[i]
                int start = intervals.get(i - 1)[1];
                int end = intervals.get(i)[0];
                newInterval = new int[]{start, start + k};

                // Ensure that the new interval does not overlap the next one
                if (newInterval[1] > end) {
                    newInterval[1] = end;
                }
            }

            // Simulate inserting the new interval
            List<int[]> newIntervals = new ArrayList<>(intervals);
            newIntervals.add(newInterval);
            newIntervals.sort(Comparator.comparingInt(interval -> interval[0]));

            // Count the connected sets with the new interval inserted
            int connectedSets = countConnectedSets(newIntervals);
            minConnectedSets = Math.min(minConnectedSets, connectedSets);
        }

        return minConnectedSets;
    }

    private static int countConnectedSets(List<int[]> intervals) {
        int connectedSets = 1;
        int currentEnd = intervals.get(0)[1];

        for (int i = 1; i < intervals.size(); i++) {
            int[] current = intervals.get(i);
            if (current[0] > currentEnd) {
                connectedSets++;
                currentEnd = current[1];
            } else {
                currentEnd = Math.max(currentEnd, current[1]);
            }
        }

        return connectedSets;
    }
}