SratNaToKopirovaniKusuKodu

package combopt;

import java.io.*;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    private BufferedReader reader;
    private int n;
    private int[][] input;

    ArrayList<Task> tasks;
    PartialSolution currentBest;

    private final int PROCESSING_TIME = 0;
    private final int RELEASE_TIME = 1;
    private final int DEADLINE = 2;

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.loadData(args[0]);
        main.doTheBratley();
        if (main.currentBest == null) {
            System.out.println("-1");
            main.solutionToFile(new int[]{-1}, args[1]);
            return;
        }
//        main.currentBest.print();
        int[] solution = main.constructDifferently(main.currentBest);
        for (int i = 0; i < solution.length; i++) {
            System.out.print(solution[i] + " ");
        }
        System.out.println();
        main.solutionToFile(solution, args[1]);
    }

    private void doTheBratley() {
        // Use dfs to search the state space
        Stack<PartialSolution> stack = new Stack<>();

        PartialSolution root = new PartialSolution(null, n);

        for (Task t : tasks) {
            // Make first partial assignments
            PartialSolution p = new PartialSolution(root, n);
            p.assignTask(t);
            stack.push(p);
        }

        PartialSolution ps;
        while (!stack.empty()) {
            ps = stack.pop();

            if (ps.unusedTasks.size() == 0) {
                if (currentBest == null) {
                    currentBest = ps;
                } else if (currentBest.finishTime > ps.finishTime) {
                    currentBest = ps;
                }
            } else {
                boolean cond1 = true;
                for (Integer i : ps.unusedTasks) {
                    if (!canBeAdded(ps, tasks.get(i))) {
                        cond1 = false;
                        break;
                    }
                }

                if (!cond1) {
                    // Didn't go through condition -> all tasks can be added to the schedule
                    continue;
                } else {
                    for (Integer i : ps.unusedTasks) {
                        PartialSolution newPs = new PartialSolution(ps, this.n);
                        newPs.assignTask(tasks.get(i));

                        if (possibleBetterSolution(newPs)) {
                            if (optimalSolution(newPs)) {
                                stack = new Stack<>();
                                stack.push(newPs);
                            } else {
                                stack.push(newPs);
                            }
                        }
                    }
                }
            }
        }
    }

    private boolean canBeAdded(PartialSolution p, Task t) {
        if (p.finishTime >= t.deadline) {
            return false;
        } else {
            if (p.finishTime < t.release) {
                return true;
            } else {
                return p.finishTime + t.processTime <= t.deadline;
            }
        }
    }

    private boolean possibleBetterSolution(PartialSolution ps) {
        if (currentBest == null) {
            return true;
        } else {
            int lb = computeLowerBound(ps);
            if (lb >= currentBest.finishTime) {
                // Eliminate
                return false;
            } else {
                return true;
            }
        }
    }

    private int computeLowerBound(PartialSolution ps) {
        int minR = Integer.MIN_VALUE;
        int pSum = 0;
        for (Integer i : ps.unusedTasks) {
            pSum += tasks.get(i).processTime;
            if (tasks.get(i).release < minR) {
                minR = tasks.get(i).release;
            }
        }
        return Integer.max(minR, ps.finishTime) + pSum;
    }

    private boolean optimalSolution(PartialSolution ps) {
        int minReleaseOfUnused = Integer.MAX_VALUE;
        for (Integer t : ps.unusedTasks) {
            if (tasks.get(t).release < minReleaseOfUnused) {
                minReleaseOfUnused = tasks.get(t).release;
            }
        }

        if (minReleaseOfUnused == Integer.MAX_VALUE) {
            // No min release found
            return false;
        }
        if (ps.finishTime <= minReleaseOfUnused) {
            return true;
        } else {
            return false;
        }
    }

    private int[] constructDifferently(PartialSolution ps) {
        int[] opt = new int[ps.taskOrder.size()];
        int taskID;

        for (int i = 0; i < ps.taskOrder.size(); i++) {
            taskID = ps.taskOrder.get(i).id;

            if (i > 0) {
                opt[taskID] = Integer.max(tasks.get(taskID).release,
                        opt[ps.taskOrder.get(i-1).id] + ps.taskOrder.get(i-1).processTime);
            } else {
                opt[taskID] = Integer.max(tasks.get(taskID).release, 0);
            }
        }

        return opt;
    }

    private int[] constructSolution(PartialSolution ps) {
        int[] starts = new int[ps.taskOrder.size()];
        int lastEnd = 0;
        int task_id;
        for (int i = 0; i < ps.taskOrder.size(); i++) {
            task_id = ps.taskOrder.get(i).id;
            if (i == 0) {
                starts[task_id] = tasks.get(task_id).release;
                lastEnd = starts[task_id] + tasks.get(task_id).processTime;
            } else {
                if (lastEnd >= tasks.get(task_id).release) {
                    starts[task_id] = lastEnd;
                    lastEnd +=  tasks.get(task_id).processTime;
                } else {
                    starts[task_id] = ps.taskOrder.get(i).release;
                    lastEnd = ps.taskOrder.get(i).release + ps.taskOrder.get(i).processTime;
                }
            }
        }
        return starts;
    }

    private void solutionToFile(int[] res, String filePath) throws IOException {
        BufferedWriter writer = new BufferedWriter(new FileWriter(filePath));
        for (int i = 0; i < res.length; i++) {
            writer.write(res[i] + "");
            if (i < res.length - 1) {
                writer.newLine();
            }
        }
        writer.flush();
        writer.close();
    }

    private void loadData(String inputPath) throws IOException {
        reader = new BufferedReader(new FileReader(inputPath));

        StringTokenizer st = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(st.nextToken());
        input = new int[n][3];
        tasks = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(reader.readLine());

            input[i][PROCESSING_TIME] = Integer.parseInt(st.nextToken());
            input[i][RELEASE_TIME] = Integer.parseInt(st.nextToken());
            input[i][DEADLINE] = Integer.parseInt(st.nextToken());

            Task t = new Task(i, input[i][PROCESSING_TIME], input[i][DEADLINE], input[i][RELEASE_TIME]);
            tasks.add(t);
        }

        currentBest = null;
    }
}