Java 8 solution using 2 maps


  • 1

    The idea is to maintain the frequency of tasks yet to be scheduled in one map and the index map of where each character was scheduled last.
    To schedule the next task, Greedily select the task that has max frequency yet to be scheduled and that is atleast n distance from the previous placement.

    public int leastInterval(char[] tasks, int n) {
            Map<Character, Long> freq = IntStream.range(0, tasks.length).
                    mapToObj(i -> tasks[i]).collect(Collectors.groupingBy(y -> y, Collectors.counting()));
            Map<Character, Integer> interval = freq.entrySet().stream().collect(Collectors.toMap(e -> e.getKey(), e->-1));
    
            int res = 0;
            int count = tasks.length;
    
            while(count != 0) {
                Character ch;
                final int r = res;
    
                Optional<Map.Entry<Character, Long>> op =  freq.entrySet().stream().filter(e -> e.getValue() > 0 && (interval.get(e.getKey()) == -1 || (r - interval.get(e.getKey())) > n)).collect(Collectors.maxBy(Map.Entry.comparingByValue()));
                if(op.isPresent()) {
                    --count;
                    ch = op.get().getKey();
                    freq.put(ch, freq.get(ch)-1);
                    interval.put(ch, res);
                }
                ++res;
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.