Не си дал кода на Employee и Department класовете, но и без тях прави впечатление, че използваш твърде много колекции и преобразувания в main метода. Може да ползваш Map<String, List<Employee>> за съхраняване на служителите по отдели още докато ги четеш от конзолата. После пускаш един стрийм върху този мап, сортираш по средно заплащане и принтираш отдела (след още един сорт на служителите му по заплата).

Нещо такова :

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        Map<String, List<Employee>> departments = new HashMap<>();
        int n = Integer.parseInt(sc.nextLine());

        for (int i = 0; i < n; i++) {
            String[] token = sc.nextLine().split(" ");

            Employee personToAdd = new Employee(token[0], Double.parseDouble(token[1]), token[2], token[3]);
            if (token.length == 5) {
                if (token[4].contains("@")) {
                    personToAdd.setEmail(token[4]);
                } else {
                    personToAdd.setAge(Integer.parseInt(token[4]));
                }
            } else if (token.length == 6) { //length == 6
                personToAdd.setEmail(token[4]);
                personToAdd.setAge(Integer.parseInt(token[5]));
            }

            departments.putIfAbsent(personToAdd.getDepartment(), new ArrayList<>());
            departments.get(personToAdd.getDepartment()).add(personToAdd);
        }

        String departmentInfo = departments.entrySet().stream()
                .sorted(department -> Comparator.comparingDouble(department.getValue().stream().mapToDouble(Employee::getSalary).average().orElse(0.0)).reversed())
                .map(department -> "Highest Average Salary: " + department.getKey() + System.lineSeparator() +
                        department.getValue().stream()
                                .sorted(Comparator.comparingDouble(Employee::getSalary).reversed())
                                .map(Object::toString)
                                .collect(Collectors.joining(System.lineSeparator())));
        System.out.println(departmentInfo);
    }

Ето едно решение от мен, с уговорката, че е по-сложно като структура от необходимото за решаването на задачата, но пък следва добри практики, които може да са ти интересни.