aboutsummaryrefslogtreecommitdiff
path: root/course_schedule_3.cpp
blob: e13d2caf05f04280e04b8a2c63ebc4b65197601b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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]; }
};