Untitled

import java.util.*;

public class TopKStudentsOptimized {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        // Step 1: Store positive and negative feedback in HashSet for fast lookup
        Set<String> positiveSet = new HashSet<>(Arrays.asList(positive_feedback));
        Set<String> negativeSet = new HashSet<>(Arrays.asList(negative_feedback));

        // Step 2: Calculate points for each student
        Map<Integer, Integer> scoreMap = new HashMap<>();
        for (int i = 0; i < report.length; i++) {
            int id = student_id[i];
            String[] words = report[i].split(" ");
            int score = 0;

            // Calculate points based on feedback words
            for (String word : words) {
                if (positiveSet.contains(word)) {
                    score += 3;
                } else if (negativeSet.contains(word)) {
                    score -= 1;
                }
            }

            // Update the student's score in the map
            scoreMap.put(id, scoreMap.getOrDefault(id, 0) + score);
        }

        // Step 3: Use a min-heap to keep track of the top k students
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1]; // Compare by score (ascending)
            }
            return a[0] - b[0]; // If scores are the same, compare by ID (ascending)
        });

        for (Map.Entry<Integer, Integer> entry : scoreMap.entrySet()) {
            int id = entry.getKey();
            int score = entry.getValue();
            minHeap.offer(new int[]{id, score});
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the student with the lowest score
            }
        }

        // Step 4: Extract results from the heap
        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll()[0]);
        }

        // Since we used a min-heap, the order is ascending; reverse it
        Collections.reverse(result);

        return result;
    }

    public static void main(String[] args) {
        TopKStudentsOptimized solution = new TopKStudentsOptimized();

        // Example 1
        String[] positive_feedback1 = {"smart", "brilliant", "studious"};
        String[] negative_feedback1 = {"not"};
        String[] report1 = {"this student is studious", "the student is smart"};
        int[] student_id1 = {1, 2};
        int k1 = 2;
        System.out.println(solution.topStudents(positive_feedback1, negative_feedback1, report1, student_id1, k1)); // Output: [1, 2]

        // Example 2
        String[] positive_feedback2 = {"smart", "brilliant", "studious"};
        String[] negative_feedback2 = {"not"};
        String[] report2 = {"this student is not studious", "the student is smart"};
        int[] student_id2 = {1, 2};
        int k2 = 2;
        System.out.println(solution.topStudents(positive_feedback2, negative_feedback2, report2, student_id2, k2)); // Output: [2, 1]
    }
}