Untitled

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

public class Test2 {
    public static int minimumDivision(int[] a, int[] b, int k) {

        List<int[]> intervals = getIntervals(a, b);

        return getMinimumDivision(intervals, k);
    }

    private static int getMinimumDivision(List<int[]> lst, int range) {
        if (lst.size() == 0) {
            return 1;
        }

        int rst = lst.size();
        for (int i = 0; i < lst.size(); i++) {
            int cnt = search(lst, i, range);
            rst = Math.min(rst, cnt);
        }

        return rst;
    }

    private static int search(List<int[]> lst, int idx, int range) {
        int prevPart = idx;
        int nextPart = binarySearch(lst, idx, range);
        return prevPart + nextPart;
    }

    private static int binarySearch(List<int[]> lst, int idx, int range) {
        int[] curr = lst.get(idx);

        int target = curr[1] + range;

        int start = idx;
        int end = lst.size() - 1;

        int mid = 0;
        while (start < end) {
            mid = start + (end - start) / 2;

            int[] temp = lst.get(mid);
            if (temp[0] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return lst.size() - idx - (mid - idx);
    }

    private static List<int[]> getIntervals(int[] a, int[] b) {
        List<int[]> intervals = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            int[] interval = new int[2];
            interval[0] = a[i];
            interval[1] = b[i];
            intervals.add(interval);
        }

        Collections.sort(intervals, (i1, i2) -> i1[0] - i2[0]);

        if (intervals.size() == 0) {
            return intervals;
        }

        int[] prev = intervals.get(0);
        List<int[]> rst = new ArrayList<>();

        for (int i = 1; i < intervals.size(); i++) {
            int[] curr = intervals.get(i);

            if (!isOverlap(prev, curr)) {
                rst.add(prev);
                prev = curr;
            } else {
                prev[1] = Math.max(prev[1], curr[1]);
            }
        }

        rst.add(prev);

        return intervals;
    }

    private static boolean isOverlap(int[] i1, int[] i2) {
        return i1[1] >= i2[0];
    }

    public static void main(String[] args) {

        int[] a = new int[] {1, 2, 6, 7, 16};
        int[] b = new int[] {5, 4, 6, 14, 19};
        int k = 2;
//
//        int[] a = new int[] {1, 2, 5, 10};
//        int[] b = new int[] {2, 4, 8, 11};
//        int k = 2;

//        int[] a = new int[] {3, 2, 3};
//        int[] b = new int[] {5, 9, 3};
//        int k = 10;

//        int[] a = new int[] {1, 3, 8, 12};
//        int[] b = new int[] {2, 5, 9, 13};
//        int k = 1;
//        k = 2;
//        k = 3;


        System.out.println(minimumDivision(a, b, k));
    }
}