Java simulate solution. easy to understand.


  • 0
    public int leastInterval(char[] tasks, int n) {
    	int interval = 0;
    	int[] count = new int[26];
    	for (int i = 0; i < tasks.length; ++i) {
    		++count[tasks[i] - 'A'];
    	}
    	List<Integer> cL = new ArrayList<Integer>();
    	for (int i = 0; i < 26; ++i) {
    		if (count[i] > 0) {
    			cL.add(count[i]);
    		}
    	}
    	if (n == 0) {//processing special condition
    		for (int x : cL) {
    			interval += x;
    		}
    		return interval;
    	}
    	while (cL.size() > 0) {
    		Collections.sort(cL);//make sure always consume the task that has the most instances
    		int removedTask = 0;
    		for (int i = 0; i <= n; ++i) {
    			int m = cL.size();
    			if (m - 1 - i < 0) {//if there's no more distinct task instance to consume, idle.
    				++interval;
    			} else {//consume a task instance
    				++interval;
    				int cC = cL.get(m - 1 - i);
    				if (cC > 1) {
    					cL.set(m - 1 - i, cC - 1);
    				} else {
    					++removedTask;//count the task types that are to be removed 
    					if (cL.size() == removedTask) {//if all task done, exit, there's no reason to idle if no more tasks
    						break;
    					}
    				}
    			}
    		}
    		for (int i=0;i < removedTask; ++i) {// for every round, remove consumed to 0 instance tasks
    			cL.remove(Integer.valueOf(1));
    		}
    	}
    	return interval;
    }

Log in to reply
 

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