Example: Get Operations

• There are n processes.
• The i-th process has resource[i] number of resources.
• All the resource[i] are distinct.
• The CPU wants processes to be arranged in increasing order of their resource[i].

The CPU does several operations to make this.

• In each operation:
  • the CPU selects an integer x and a process with number of resources x .
  • It then places all processes with resource values less than x before the processes with resource values greater than or equal to x, maintaining their original relative order.

Find the lexicographically smallest sequence of Xs that the CPU chooses, such that it takes the minimum number of operations to complete the task. If the minimum number of operations = 0, then return a sequence only containing the integer -1.

Approach

We use BFS to explore states (different resource orders).

At each step, we simulate all possible partition values x (unique values in the current list).

We store visited states (as strings) to avoid loops.

When we find the first sorted list, we stop (since BFS guarantees shortest path).

import java.util.*;

public class CPUProcessSorter {

    public static List<Integer> getMinOperations(int[] resources) {
        if (isSorted(resources)) {
            return List.of(-1);
        }

        Queue<State> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.offer(new State(resources, new ArrayList<>()));
        visited.add(Arrays.toString(resources));

        while (!queue.isEmpty()) {
            State current = queue.poll();

            if (isSorted(current.resources)) {
                return current.operations;
            }

            // Try every unique resource value as a possible x
            TreeSet<Integer> seen = new TreeSet<>();
            for (int val : current.resources) {
                seen.add(val);
            }

            for (int x : seen) {
                int[] newResources = applyOperation(current.resources, x);
                String key = Arrays.toString(newResources);

                if (!visited.contains(key)) {
                    visited.add(key);
                    List<Integer> newOps = new ArrayList<>(current.operations);
                    newOps.add(x);
                    queue.offer(new State(newResources, newOps));
                }
            }
        }

        return List.of(-1); // fallback, though this shouldn't be hit
    }

    // Simulates the stable partition operation for a given pivot x
    private static int[] applyOperation(int[] arr, int x) {
        List<Integer> less = new ArrayList<>();
        List<Integer> greaterEqual = new ArrayList<>();

        for (int num : arr) {
            if (num < x) {
                less.add(num);
            } else {
                greaterEqual.add(num);
            }
        }

        // Combine both parts
        int[] result = new int[arr.length];
        int idx = 0;
        for (int val : less) result[idx++] = val;
        for (int val : greaterEqual) result[idx++] = val;
        return result;
    }

    private static boolean isSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }


    private static class State {
        int[] resources;
        List<Integer> operations;

        State(int[] resources, List<Integer> operations) {
            this.resources = resources.clone(); // important to copy array
            this.operations = operations;
        }
    }

    // For testing
    public static void main(String[] args) {
        int[] input1 = {4, 3, 2, 1};
        int[] input2 = {1, 2, 3, 4};
        int[] input3 = {3, 1, 2};

        System.out.println(getMinOperations(input1)); // Example: [3, 2]
        System.out.println(getMinOperations(input2)); // [-1]
        System.out.println(getMinOperations(input3)); // [2]
    }
}