minimum-number-of-seconds-to-make-mountain-height-zero

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer <code>mountainHeight</code> denoting the height of a mountain.

You are also given an integer array <code>workerTimes</code> representing the work time of workers in seconds.

The workers work simultaneously to reduce the height of the mountain. For worker <code>i</code>:

<ul>
	<li>To decrease the mountain&#39;s height by <code>x</code>, it takes <code>workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x</code> seconds. For example:

	<ul>
		<li>To reduce the height of the mountain by 1, it takes <code>workerTimes[i]</code> seconds.</li>
		<li>To reduce the height of the mountain by 2, it takes <code>workerTimes[i] + workerTimes[i] * 2</code> seconds, and so on.</li>
	</ul>
	</li>
</ul>

Return an integer representing the minimum number of seconds required for the workers to make the height of the mountain 0.

&nbsp;
Example 1:

<div class="example-block">
Input: mountainHeight = 4, workerTimes = [2,1,1]

Output: 3

Explanation:

One way the height of the mountain can be reduced to 0 is:

<ul>
	<li>Worker 0 reduces the height by 1, taking <code>workerTimes[0] = 2</code> seconds.</li>
	<li>Worker 1 reduces the height by 2, taking <code>workerTimes[1] + workerTimes[1] * 2 = 3</code> seconds.</li>
	<li>Worker 2 reduces the height by 1, taking <code>workerTimes[2] = 1</code> second.</li>
</ul>

Since they work simultaneously, the minimum time needed is <code>max(2, 3, 1) = 3</code> seconds.
</div>

Example 2:

<div class="example-block">
Input: mountainHeight = 10, workerTimes = [3,2,2,4]

Output: 12

Explanation:

<ul>
	<li>Worker 0 reduces the height by 2, taking <code>workerTimes[0] + workerTimes[0] * 2 = 9</code> seconds.</li>
	<li>Worker 1 reduces the height by 3, taking <code>workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12</code> seconds.</li>
	<li>Worker 2 reduces the height by 3, taking <code>workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12</code> seconds.</li>
	<li>Worker 3 reduces the height by 2, taking <code>workerTimes[3] + workerTimes[3] * 2 = 12</code> seconds.</li>
</ul>

The number of seconds needed is <code>max(9, 12, 12, 12) = 12</code> seconds.
</div>

Example 3:

<div class="example-block">
Input: mountainHeight = 5, workerTimes = [1]

Output: 15

Explanation:

There is only one worker in this example, so the answer is <code>workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= mountainHeight &lt;= 105</code></li>
	<li><code>1 &lt;= workerTimes.length &lt;= 104</code></li>
	<li><code>1 &lt;= workerTimes[i] &lt;= 106</code></li>
</ul>

minNumberOfSeconds

Minimum Number of Seconds to Make Mountain Height Zero

Greedy

Array

Math

Binary Search

Heap (Priority Queue)

给你一个整数 <code>mountainHeight</code> 表示山的高度。

同时给你一个整数数组 <code>workerTimes</code>，表示工人们的工作时间（单位：秒）。

工人们需要 同时 进行工作以 降低 山的高度。对于工人 <code>i</code> :

<ul>
	<li>山的高度降低 <code>x</code>，需要花费 <code>workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x</code> 秒。例如：

	<ul>
		<li>山的高度降低 1，需要 <code>workerTimes[i]</code> 秒。</li>
		<li>山的高度降低 2，需要 <code>workerTimes[i] + workerTimes[i] * 2</code> 秒，依此类推。</li>
	</ul>
	</li>
</ul>

返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。

&nbsp;

示例 1：

<div class="example-block">
输入： mountainHeight = 4, workerTimes = [2,1,1]

输出： 3

解释：

将山的高度降低到 0 的一种方式是：

<ul>
	<li>工人 0 将高度降低 1，花费 <code>workerTimes[0] = 2</code> 秒。</li>
	<li>工人 1 将高度降低 2，花费 <code>workerTimes[1] + workerTimes[1] * 2 = 3</code> 秒。</li>
	<li>工人 2 将高度降低 1，花费 <code>workerTimes[2] = 1</code> 秒。</li>
</ul>

因为工人同时工作，所需的最少时间为 <code>max(2, 3, 1) = 3</code> 秒。
</div>

示例 2：

<div class="example-block">
输入： mountainHeight = 10, workerTimes = [3,2,2,4]

输出： 12

解释：

<ul>
	<li>工人 0 将高度降低 2，花费 <code>workerTimes[0] + workerTimes[0] * 2 = 9</code> 秒。</li>
	<li>工人 1 将高度降低 3，花费 <code>workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12</code> 秒。</li>
	<li>工人 2 将高度降低 3，花费 <code>workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12</code> 秒。</li>
	<li>工人 3 将高度降低 2，花费 <code>workerTimes[3] + workerTimes[3] * 2 = 12</code> 秒。</li>
</ul>

所需的最少时间为 <code>max(9, 12, 12, 12) = 12</code> 秒。
</div>

示例 3：

<div class="example-block">
输入： mountainHeight = 5, workerTimes = [1]

输出： 15

解释：

这个示例中只有一个工人，所以答案是 <code>workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15</code> 秒。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= mountainHeight &lt;= 105</code></li>
	<li><code>1 &lt;= workerTimes.length &lt;= 104</code></li>
	<li><code>1 &lt;= workerTimes[i] &lt;= 106</code></li>
</ul>