Task Test

/*
     * Тестовое задание:

     N студентов стоят в очереди за стипендией. Каждый студент имеет учебный рейтинг. Деканат должен выдать стипендию таким образом, чтобы:
     * каждый студент получил хотя бы 1 рубль,
     * студенты с более высоким рейтингом получили больше рублей, чем их соседи в очереди.
     Копеек в деканате нет. Какое минимальное количество рублей должно быть у деканата?

     На вход подаётся массив из N элементов, содержащий рейтинги для каждого студента.
     На выходе ожидается число, обозначающее минимальное количество рублей, которых должно хватить студентам.

     Пример.
     Вход: [1, 2, 3, 4, 5, 3, 2, 1, 2, 6, 5, 4, 3, 3, 2, 1, 1, 3, 3, 3, 4, 2]
     Выход: 47
     */


import java.util.*;

public class TouchTest {

    static class Student {
        public Student(int id) {
            this.id = id;
        }

        int id;
        List<Student> moreThan = new ArrayList<>();
        List<Student> lessThan = new ArrayList<>();
        int pay = 0;

        public String toString() {
            return "Student{" +
                    "id=" + id +
                    ", moreThan=" + moreThan +
                    '}';
        }
    }

    public static void main(String[] args) {

        Integer[] arr = {1, 2, 3, 4, 5, 3, 2, 1, 2, 6, 5, 4, 3, 3, 2, 1, 1, 3, 3, 3, 4, 2};
        calculationSum(arr);

    }

    private static Set<Student> getMinorStudents(Collection<Student> students) {
        Set<Student> set = new HashSet<>();
        for (Student student : students) {
            if (student.moreThan.isEmpty()) {
                set.add(student);
            }
        }
        return set;
    }

    private static void calculationSum(Integer[] arr) {
        //создаем пул студентов
        Map<Integer, Student> studentMap = new HashMap<>();
        for (int j = 0; j < arr.length; j++) {
            studentMap.put(j, new Student(j));
        }

        // строим отношения студентов
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] < arr[i]) {
                studentMap.get(i - 1).lessThan.add(studentMap.get(i));
                studentMap.get(i).moreThan.add(studentMap.get(i - 1));
            }

            if (arr[i - 1] > arr[i]) {
                studentMap.get(i - 1).moreThan.add(studentMap.get(i));
                studentMap.get(i).lessThan.add(studentMap.get(i - 1));
            }
        }

        // текущая степендия (минимальная)
        int currentPay = 1;

        // студенты  - с минимальной стипендией
        Set<Student> currentPayStudents = getMinorStudents(studentMap.values());

        while (!currentPayStudents.isEmpty()) {
            Set<Student> nextPayStudents = new HashSet<>();
            for (Student s : currentPayStudents) {
                // стипендия студента = уровню если другая ветка не установила более высокую
                s.pay = Math.max(s.pay, currentPay);
                // студенты со степендией на уровень выше
                nextPayStudents.addAll(s.lessThan);
            }
            // следующая итерация
            currentPayStudents = nextPayStudents;
            currentPay++;
        }

        // выводим стипендии и итоговую сумму
        int sum = 0;
        for (Student s : studentMap.values()) {
            System.out.format("pay=%d, rate = %d \n", s.pay, arr[s.id]);
            sum += s.pay;
        }
        System.out.format("итоговая сумма: %d", sum);
    }

}