leetcode

commit 7792bb7d4ecaf9449b7a3c88936af32816eb881a
parent 0067ed4cdb9326783e89a98ae44f32953f357040
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 30 Nov 2025 18:32:01 -0700

2141. maximum running time of n computers

Diffstat:
M
max_running_time_n_computer.c
 | 
39
++++++++++++++++-----------------------
A
max_running_time_n_computer.py
 | 
39
+++++++++++++++++++++++++++++++++++++++

2 files changed, 55 insertions(+), 23 deletions(-)
diff --git a/max_running_time_n_computer.c b/max_running_time_n_computer.c
@@ -1,7 +1,5 @@
 // 2141. Maximum Running Time of N Computers
-#include <math.h>
-#include <stdbool.h>
-#include <stdio.h>
+#include "leetcode.h"
 
 /*
  * you have 'n' computers. you are given the integer 'n' and a 0-indexed integer
@@ -17,30 +15,25 @@
  * simultaneously.
  */
 
-bool check(int n, int *batteries, int batteries_size, long long time) {
-  long long total = time * n, sum = 0;
-  for (int i = 0; i < batteries_size; i++) {
-    sum += fmin(time, batteries[i]);
-    if (sum >= total)
-      return true;
-  }
-  return false;
-}
+int cmp(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); }
 
-long long maxRunTime(int n, int *batteries, int batteries_size) {
-  long long left = 0, right = 1e14;
-  while (left < right) {
-    long long mid = right - (right - left) / 2;
-    if (check(n, batteries, batteries_size, mid))
-      left = mid;
-    else
-      right = mid - 1;
+long long maxRunTime(int n, int *batteries, int batteriesSize) {
+  long long total = 0;
+  for (int i = 0; i < batteriesSize; i++)
+    total += batteries[i];
+  qsort(batteries, batteriesSize, sizeof(int), cmp);
+  for (int i = batteriesSize - 1; i >= 0; i--) {
+    if (batteries[i] > total / n) {
+      total -= batteries[i];
+      n--;
+    } else
+      break;
   }
-  return left;
+  return total / n;
 }
 
 int main() {
   int b1[] = {3, 3, 3}, b2[] = {1, 1, 1, 1};
-  printf("%lld\n", maxRunTime(2, b1, 3)); // expect: 4
-  printf("%lld\n", maxRunTime(2, b2, 4)); // expect: 2
+  printf("%lld\n", maxRunTime(2, b1, ARRAY_SIZE(b1))); // expect: 4
+  printf("%lld\n", maxRunTime(2, b2, ARRAY_SIZE(b2))); // expect: 2
 }
diff --git a/max_running_time_n_computer.py b/max_running_time_n_computer.py
@@ -0,0 +1,39 @@
+# 2141. Maximum Running Time of N Computers
+
+"""
+you have 'n' computers. you are given the integer 'n' and a 0-indexed integer
+array 'batteries' where the i'th battery can run a computer for
+'batteries[i]' minutes. you are interested in running all 'n' computers
+simultaneously using the given batteries. initially, you can insert at most
+one battery into each computer. after that and at any integer time moment,
+you can remove a battery from a computer and insert another battery any
+number of times. the inserted battery can be a totally new battery or a
+battery forom another computer. you may assume that the removing and
+inserting process takes no time. note that the batteries canot be recharged.
+return the maximum number of minutes you can run all the 'n' computers
+simultaneously.
+"""
+
+
+class Solution(object):
+    def maxRunTime(self, n, batteries):
+        """
+        :type n: int
+        :type batteries: List[int]
+        :rtype: int
+        """
+        total = sum(batteries)
+        batteries.sort()
+        for i in range(len(batteries) - 1, -1, -1):
+            if batteries[i] > total // n:
+                total -= batteries[i]
+                n -= 1
+            else:
+                break
+        return total // n
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maxRunTime(n=2, batteries=[3, 3, 3]))
+    print(obj.maxRunTime(n=2, batteries=[1, 1, 1, 1]))