Java 97ms nlogn solution beats 95%


  • 0
    S

    Whenever we find a course can not fit in current assignment we remove the course which has the greatest duration from the chosen courses

    public int scheduleCourse(int[][] courses) {
            TreeMap<Integer, Integer> map = new TreeMap<>();
            Arrays.sort(courses, new Comparator<int[]>(){
                public int compare(int[] i1, int[] i2){
                    if(i1[1] == i2[1]) return i1[0] - i2[0];
                    return i1[1] - i2[1];
                }
            });
            int cur = 0;
            for(int[] i : courses){
                cur += i[0];
                if(cur <= i[1]) map.put(i[0], map.getOrDefault(i[0], 0) + 1);
                else{
                    Integer key = map.lastKey();
                    if(key != null && key > i[0]){
                        map.put(i[0], map.getOrDefault(i[0], 0) + 1);
                        map.put(key, map.get(key) - 1);
                        if(map.get(key) == 0) map.remove(key);
                        cur = cur - key;
                    }else
                        cur -= i[0];
                }
            }
            int count = 0;
            for(Map.Entry<Integer, Integer> e : map.entrySet())
                count += e.getValue();
           	return count;
        }
    

Log in to reply
 

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