aboutsummaryrefslogtreecommitdiff
path: root/other/course_schedule_3.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/course_schedule_3.cpp')
-rw-r--r--other/course_schedule_3.cpp27
1 files changed, 27 insertions, 0 deletions
diff --git a/other/course_schedule_3.cpp b/other/course_schedule_3.cpp
new file mode 100644
index 0000000..e13d2ca
--- /dev/null
+++ b/other/course_schedule_3.cpp
@@ -0,0 +1,27 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int scheduleCourse(vector<vector<int>> &courses) {
+ int time = 0;
+ priority_queue<int> pq;
+ sort(courses.begin(), courses.end(), compare);
+ for (int i = 0; i < courses.size(); i++) {
+ if (time + courses[i][0] <= courses[i][1]) {
+ time += courses[i][0];
+ pq.push(courses[i][0]);
+ } else {
+ if (!pq.empty() && pq.top() > courses[i][0]) {
+ pq.pop();
+ time -= pq.top();
+ time += courses[i][0];
+ pq.push(courses[i][0]);
+ }
+ }
+ }
+ return pq.size();
+ }
+
+private:
+ static bool compare(vector<int> a, vector<int> b) { return a[1] < b[1]; }
+};