diff options
Diffstat (limited to 'other/course_schedule_3.cpp')
-rw-r--r-- | other/course_schedule_3.cpp | 27 |
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]; } +}; |