You are given a set \(\mathbb{M}\) of numbers of milestone, with size \(N\). Every week, you finish exactly one milestone of one project. You must work every week. You can’t work on two milestones from the same project for two consecutive weeks.
Once all the milestones of all projects are finished, or if it must violate the rules to work on the remaining milestones, you will stop working. Return the maximum number of weeks, for which you can work without violating the rules.
Constraints:
\(1\)\(\;\leq\;\)\(N\)\(\;\leq\;\)\(1\)\(0 \vphantom{1 0}^{5}\)\(;\,\)
\(1\)\(\;\leq\;\)\(\mathbb{M} \vphantom{ \mathbb{M}}_{\left[n\right]}\)\(\;\leq\;\)\(1\)\(0 \vphantom{1 0}^{9}\)\(,\,\)\(\;\mathtt{for}\;\)\(n\)\(\;=\;\)\(1\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(N\)\(;\,\)
(The story is so bad, I can’t help thinking another one. Very simply, we may think there are several piles of pebbles, and we have to take them, one by one, but not taking two in a row from the same pile. How many pebbles can we take consecutively?
Alternatively, I offer a more interesting one. In a human mission to Mars, the main dynamo is out of order. There has been smaller, supplementary dynamos on the spaceship. We plan to run one every night. If a dynamo is run for two night, it will overheat. Given limited amount of fuels, how many night can we survive before the rescue team arrive?)
The problem appears to be very complicated, but the answer was rather short. I saw the complexity of solution to be \(\mathscr{O}\)\(\left[\vphantom{N}\right.\)\(N\)\(\left.\vphantom{N}\right]\), which surprised me, and then I really came up of the solution myself.
In the ideal case, every project is finished, and every milestone is used up. That won’t happen, if some projects remains, but when do they? If two projects still remain, we can do them alternatively, so there will be only one project remaining, if at all.
Regardless of the complexity, suppose \(\mathbb{M}\)\(\;=\;\)\(\left\{\vphantom{M \vphantom{ M}_{0} ,\, \,\dotsc\, ,\, M \vphantom{ M}_{N \,-\, 1}}\right.\)\(M \vphantom{ M}_{0}\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(M \vphantom{ M}_{N \,-\, 1}\)\(\left.\vphantom{M \vphantom{ M}_{0} ,\, \,\dotsc\, ,\, M \vphantom{ M}_{N \,-\, 1}}\right\}\) is sorted in descending order. What if we always consume \(M \vphantom{ M}_{0}\) alternately with \(M \vphantom{ M}_{1}\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(M \vphantom{ M}_{N \,-\, 1}\), until \(M \vphantom{ M}_{0}\)\(\,-\,\)\(M \vphantom{ M}_{1}\) milestones are used up?
If so, we have a pair of two largest projects, both of length \(M \vphantom{ M}_{1}\). Smaller projects can be consumed alternately with the pair, while keeping the pair even. Once the tie is intact, they will be cancelled exactly.
Otherwise, if \(m\)\(\,+\,\)\(1\)\(\;>\;\)\(0\) milestones are left finally from \(M \vphantom{ M}_{0}\), we are free to subtract a final one, leaving \(m\) milestones. This is because we cancel projects two by two, and the order doesn’t pose restriction on the final step, even if some pairs overlap. Since we have consumed all other projects and still can’t cancel \(M \vphantom{ M}_{0}\), we have already done our best.
Sorting takes \(\mathscr{O}\)\(\left[\vphantom{N \,\mathrm{log}\, N}\right.\)\(N\)\(\,\mathrm{log}\,\)\(N\)\(\left.\vphantom{N \,\mathrm{log}\, N}\right]\), which we can’t do. However, we only have to know the answer within \(\mathscr{O}\)\(\left[\vphantom{N}\right.\)\(N\)\(\left.\vphantom{N}\right]\), and at least we may find \(M \vphantom{ M}_{0}\)\(\;\in\;\)\(\mathbb{M}\), from the discussion above, the answer is simply \(\,\mathrm{max}\,\)\(\left(\vphantom{0 ,\, M \vphantom{ M}_{0} \,-\, M \vphantom{ M}_{1} \,-\, \,\dotsc\, \,-\, M \vphantom{ M}_{N \,-\, 1} \,-\, 1}\right.\)\(0\)\(,\,\)\(M \vphantom{ M}_{0}\)\(\,-\,\)\(M \vphantom{ M}_{1}\)\(\,-\,\)\(\,\dotsc\,\)\(\,-\,\)\(M \vphantom{ M}_{N \,-\, 1}\)\(\,-\,\)\(1\)\(\left.\vphantom{0 ,\, M \vphantom{ M}_{0} \,-\, M \vphantom{ M}_{1} \,-\, \,\dotsc\, \,-\, M \vphantom{ M}_{N \,-\, 1} \,-\, 1}\right)\). The trivial case, that there is only \(1\) project, also applies. There might be a shorter proof, but I am proud of my independent thinking.
# 1953. Maximum Number of Weeks for Which You Can Work [medium]
#! /usr/bin/env python3
import typing as TYPE
def main():
bound = [5, 2, 1]
solution = Solution()
number = solution.
print("There are", number, "weeks.")
# 7
class Solution:
def find_number_round(self, array: TYPE.List[int]) -> int:
total = sum(array)
big = max(array)
remain = total - big
if (remain < big): return (total + remain - big + 1)
return total
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
main()
❧ August 5, 2021