leetcode: Task Scheduler

문제 조건

• cpu에 태스크가 들어올건데 태스크의 순서는 맘대로 실행할 수 있다.
• 각 태스크는 한 시간 단위로 수행되고, 태스크를 실행하거나 idle 상태에 있을 수 있다.
• 두 개의 동일한 태스크를 실행하기 위한 사이에는 최소 n개의 태스크/idle이 있어야 한다.

흠... 일단은 그냥 가장 자주 나오는 글자를 배치하고 그 사이에 n개의 빈 칸을 둔 뒤에 다른 애들을 적절히 배치하면 될 것 같다고 생각했다.

class Solution {
	public int leastInterval(char[] tasks, int n) {
		int[] frequency = new int[26];
		for (int task : tasks) {
			frequency[task - 'A']++;
		}

		Arrays.sort(frequency);

		int maxFrequency = frequency[25];
		int betweenTime = (maxFrequency - 1) * n;

		int index = frequency.length - 2;
		while (index >= 0 && betweenTime > 0) {
			betweenTime -= Math.min(maxFrequency - 1, frequency[index]);
			index--;
		}
		betweenTime = Math.max(0, betweenTime);

		return betweenTime + tasks.length;
	}
}