Skip to content

3281. Maximize Score of Numbers in Ranges 👍

  • Time: $O(n\log(\max - \min))$
  • Space: $O(\texttt{sort})$
 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
28
29
30
class Solution {
 public:
  int maxPossibleScore(vector<int>& start, int d) {
    ranges::sort(start);

    long l = 0;
    long r = (start.back() + d) - start.front() + 1;

    while (l < r) {
      const long m = (l + r) / 2;
      if (isPossible(start, d, m))
        l = m + 1;
      else
        r = m;
    }

    return l - 1;
  }

 private:
  bool isPossible(const vector<int>& start, int d, long m) {
    int lastPick = start[0];
    for (int i = 1; i < start.size(); ++i) {
      if (lastPick + m > start[i] + d)
        return false;
      lastPick = max(lastPick + m, static_cast<long>(start[i]));
    }
    return true;
  }
};

 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
28
class Solution {
  public int maxPossibleScore(int[] start, int d) {
    Arrays.sort(start);

    long l = 0;
    long r = (start[start.length - 1] + d) - start[0] + 1;

    while (l < r) {
      final long m = (l + r) / 2;
      if (isPossible(start, d, m))
        l = m + 1;
      else
        r = m;
    }

    return (int) (l - 1);
  }

  private boolean isPossible(int[] start, int d, long m) {
    long lastPick = start[0];
    for (int i = 1; i < start.length; ++i) {
      if (lastPick + m > start[i] + d)
        return false;
      lastPick = Math.max(lastPick + m, (long) start[i]);
    }
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxPossibleScore(self, start: list[int], d: int) -> int:
    def isPossible(m: int) -> bool:
      lastPick = start[0]
      for i in range(1, len(start)):
        if lastPick + m > start[i] + d:
          return False
        lastPick = max(lastPick + m, start[i])
      return True

    start.sort()

    maxScore = (start[-1] + d) - start[0] + 1
    l = bisect.bisect_left(range(maxScore), True,
                           key=lambda m: not isPossible(m))
    return l - 1