Partition - JAVA

// Author : Saurav Kalsoor
// Partition - JAVA

import java.util.*;

public class Test {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        int x = sc.nextInt();

        ArrayList<Integer> arr = new ArrayList<>();
        for(int i = 0;i < n; i++){
            arr.add(sc.nextInt());
        }

        System.out.println(partition(n, k, x, arr));
    }

    public static int partition(int n, int k, int x, ArrayList<Integer> arr){
        Collections.sort(arr);
        int count = 1;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i = 1;
        while(i < n){
            int diff = arr.get(i) - arr.get(i-1);
            if(diff > k){
                count++;
                pq.offer(diff);
            }
            i++;
        }

        while(!pq.isEmpty() && x > 0){
            int diff = pq.poll();
            int req = (diff - 1)/k;
            if(x >= req){
                x -= req;
                count--;
            }else{
                break;
            }
        }

        return count;
    }

}