leetcode

commit 780df78caa1e1603146ce55fa2b9be345c397374
parent 38fecc903b4a014cd562d14184b5c0f8770374af
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  6 Jan 2024 12:27:33 +0000

Daily Problem

Diffstat:
A
Problems/1235.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/1235.cpp b/Problems/1235.cpp
@@ -0,0 +1,21 @@
+class Solution {
+  public:
+    int jobScheduling(const vector<int> &startTime, const vector<int> &endTime,
+                      const vector<int> &profit) const {
+        static int indices[50001];
+        const int n = profit.size();
+
+        iota(begin(indices), begin(indices) + n, 0);
+        sort(begin(indices), begin(indices) + n,
+             [&endTime](int a, int b) { return endTime[a] < endTime[b]; });
+
+        map<int, int> dp = {{0, 0}};
+        for (int i = 0; i < n; i++) {
+            const int idx = indices[i];
+            const int crnt = profit[idx] + prev(dp.upper_bound(startTime[idx]))->second;
+            if (crnt > dp.rbegin()->second) dp[endTime[idx]] = crnt;
+        }
+
+        return dp.rbegin()->second;
+    }
+};
diff --git a/README.md b/README.md
@@ -623,6 +623,7 @@ for solving problems.
 |  1227  |   Medium   | [Airplane Seat Assignment Probability](Problems/1227.cpp)                                          |
 |  1232  |    Easy    | [Check If It Is a Straight Line](Problems/1232.cpp)                                                |
 |  1233  |   Medium   | [Remove Sub-Folders from the Filesystem](Problems/1233.cpp)                                        |
+|  1235  |    Hard    | [Maximum Profit in Job Scheduling](Problems/1235.cpp)                                              |
 |  1237  |   Medium   | [Find Positive Integer Solution for a Given Equation](Problems/1237.cpp)                           |
 |  1238  |   Medium   | [Circular Permutation in Binary Representation](Problems/1238.cpp)                                 |
 |  1247  |   Medium   | [Minimum Swaps to Make Strings Equal](Problems/1247.cpp)                                           |