add 630

fishercoder1534 · fishercoder1534 · commit ccab7b0bcf38 · 2017-07-25T08:35:29.000-07:00
diff --git a/README.md b/README.md
@@ -35,6 +35,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |634|[Find the Derangement of An Array](https://leetcode.com/problems/find-the-derangement-of-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_634.java) | O(n) |O(1) | Medium | Math
 |633|[Sum of Square Numbers](https://leetcode.com/problems/sum-of-square-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_633.java) | O(logn) |O(1) | Easy | Binary Search
 |632|[Smallest Range](https://leetcode.com/problems/smallest-range/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_632.java) | O(n*logk) |O(k) | Hard| Heap
+|630|[Course Schedule III](https://leetcode.com/problems/course-schedule-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_630.java) | O(n*logn) |O(n) | Hard| Heap, Greedy
 |628|[Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_628.java) | O(nlogn) |O(1) | Easy |
 |625|[Minimum Factorization](https://leetcode.com/problems/minimum-factorization/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_625.java) | O(?) |O(?) | Medium | 
 |624|[Maximum Distance in Arrays](https://leetcode.com/problems/maximum-distance-in-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_624.java) | O(nlogn) |O(1) | Easy | Sort, Array
diff --git a/src/main/java/com/fishercoder/solutions/_630.java b/src/main/java/com/fishercoder/solutions/_630.java
@@ -0,0 +1,59 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+import java.util.PriorityQueue;
+
+/**
+ * 630. Course Schedule III
+ *
+ * There are n different online courses numbered from 1 to n.
+ * Each course has some duration(course length) t and closed on dth day.
+ * A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
+
+ Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
+
+ Example:
+ Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
+ Output: 3
+
+ Explanation:
+ There're totally 4 courses, but you can take 3 courses at most:
+ First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
+ Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
+ Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
+ The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.
+
+ Note:
+ The integer 1 <= d, t, n <= 10,000.
+ You can't take two courses simultaneously.
+ */
+public class _630 {
+    /**Reference: https://discuss.leetcode.com/topic/93790/short-java-code-using-priorityqueue
+     * Sort by finish date!!! This is greedy! We should take those classes that finish early first.*/
+    public int scheduleCourse(int[][] courses) {
+        Arrays.sort(courses, (a,b) -> a[1] - b[1]);
+        int day = 0;
+        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
+        for (int[] course : courses) {
+            day += course[0];
+            maxHeap.offer(course[0]);
+            if (day > course[1]) {
+                day -= maxHeap.poll();//drop the previous courses that took the most time
+            }
+        }
+        return maxHeap.size();
+    }
+
+    public static void main(String... args) {
+        _630 test = new _630();
+        int[][] courses = new int[][]{
+                {100, 200},
+                {200, 1300},
+                {1000, 1250},
+                {2000, 3200},
+                {300, 1200}
+        };
+        test.scheduleCourse(courses);
+        System.out.println("Finished..");
+    }
+}
