Skip to content

Commit 00bcff0

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1870. Minimum Speed to Arrive on Time
1 parent 4b977a6 commit 00bcff0

File tree

6 files changed

+212
-57
lines changed

6 files changed

+212
-57
lines changed

‎solution/1800-1899/1870.Minimum Speed to Arrive on Time/README.md

Lines changed: 74 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -84,16 +84,15 @@ class Solution:
8484
for i, d in enumerate(dist):
8585
res += (d / speed) if i == len(dist) - 1 else math.ceil(d / speed)
8686
return res <= hour
87-
if len(dist) - 1 >= hour:
88-
return -1
89-
l, r = 1, 10 ** 7
90-
while l < r:
91-
m = (l + r) >> 1
92-
if arrive_on_time(m):
93-
r = m
87+
88+
left, right = 1, 10 ** 7
89+
while left < right:
90+
mid = (left + right) >> 1
91+
if arrive_on_time(mid):
92+
right = mid
9493
else:
95-
l = m + 1
96-
return l
94+
left = mid + 1
95+
return left if arrive_on_time(left) else -1
9796
```
9897

9998
### **Java**
@@ -103,19 +102,16 @@ class Solution:
103102
```java
104103
class Solution {
105104
public int minSpeedOnTime(int[] dist, double hour) {
106-
if (dist.length - 1 >= hour) {
107-
return -1;
108-
}
109-
int l = 1, r = 10000000;
110-
while (l < r) {
111-
int m = (l + r) >> 1;
112-
if (arriveOnTime(dist, m, hour)) {
113-
r = m;
105+
int left = 1, right = (int) 1e7;
106+
while (left < right) {
107+
int mid = (left + right) >> 1;
108+
if (arriveOnTime(dist, mid, hour)) {
109+
right = mid;
114110
} else {
115-
l = m + 1;
111+
left = mid + 1;
116112
}
117113
}
118-
return l;
114+
return arriveOnTime(dist, left, hour) ? left : -1;
119115
}
120116

121117
private boolean arriveOnTime(int[] dist, int speed, double hour) {
@@ -129,6 +125,35 @@ class Solution {
129125
}
130126
```
131127

128+
### **C++**
129+
130+
```cpp
131+
class Solution {
132+
public:
133+
int minSpeedOnTime(vector<int>& dist, double hour) {
134+
int left = 1, right = 1e7;
135+
while (left < right) {
136+
int mid = (left + right) >> 1;
137+
if (arriveOnTime(dist, mid, hour)) {
138+
right = mid;
139+
} else {
140+
left = mid + 1;
141+
}
142+
}
143+
return arriveOnTime(dist, left, hour) ? left : -1;
144+
}
145+
146+
bool arriveOnTime(vector<int>& dist, int speed, double hour) {
147+
double res = 0;
148+
for (int i = 0; i < dist.size(); ++i) {
149+
double cost = dist[i] * 1.0 / speed;
150+
res += (i == dist.size() - 1 ? cost : ceil(cost));
151+
}
152+
return res <= hour;
153+
}
154+
};
155+
```
156+
132157
### **JavaScript**
133158

134159
```js
@@ -165,6 +190,36 @@ class Solution {
165190
}
166191
```
167192

193+
### **Go**
194+
195+
```go
196+
func minSpeedOnTime(dist []int, hour float64) int {
197+
n := len(dist)
198+
left, right := 1, int(1e7)
199+
for left < right {
200+
mid := (left + right) >> 1
201+
if arriveOnTime(dist, n, float64(mid), hour) {
202+
right = mid
203+
} else {
204+
left = mid + 1
205+
}
206+
}
207+
if arriveOnTime(dist, n, float64(left), hour) {
208+
return left
209+
}
210+
return -1
211+
}
212+
213+
func arriveOnTime(dist []int, n int, speed, hour float64) bool {
214+
var cost float64
215+
for _, v := range dist[:n-1] {
216+
cost += math.Ceil(float64(v) / speed)
217+
}
218+
cost += float64(dist[n-1]) / speed
219+
return cost <= hour
220+
}
221+
```
222+
168223
### **...**
169224

170225
```

‎solution/1800-1899/1870.Minimum Speed to Arrive on Time/README_EN.md

Lines changed: 74 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -74,36 +74,32 @@ class Solution:
7474
for i, d in enumerate(dist):
7575
res += (d / speed) if i == len(dist) - 1 else math.ceil(d / speed)
7676
return res <= hour
77-
if len(dist) - 1 >= hour:
78-
return -1
79-
l, r = 1, 10 ** 7
80-
while l < r:
81-
m = (l + r) >> 1
82-
if arrive_on_time(m):
83-
r = m
77+
78+
left, right = 1, 10 ** 7
79+
while left < right:
80+
mid = (left + right) >> 1
81+
if arrive_on_time(mid):
82+
right = mid
8483
else:
85-
l = m + 1
86-
return l
84+
left = mid + 1
85+
return left if arrive_on_time(left) else -1
8786
```
8887

8988
### **Java**
9089

9190
```java
9291
class Solution {
9392
public int minSpeedOnTime(int[] dist, double hour) {
94-
if (dist.length - 1 >= hour) {
95-
return -1;
96-
}
97-
int l = 1, r = 10000000;
98-
while (l < r) {
99-
int m = (l + r) >> 1;
100-
if (arriveOnTime(dist, m, hour)) {
101-
r = m;
93+
int left = 1, right = (int) 1e7;
94+
while (left < right) {
95+
int mid = (left + right) >> 1;
96+
if (arriveOnTime(dist, mid, hour)) {
97+
right = mid;
10298
} else {
103-
l = m + 1;
99+
left = mid + 1;
104100
}
105101
}
106-
return l;
102+
return arriveOnTime(dist, left, hour) ? left : -1;
107103
}
108104

109105
private boolean arriveOnTime(int[] dist, int speed, double hour) {
@@ -117,6 +113,35 @@ class Solution {
117113
}
118114
```
119115

116+
### **C++**
117+
118+
```cpp
119+
class Solution {
120+
public:
121+
int minSpeedOnTime(vector<int>& dist, double hour) {
122+
int left = 1, right = 1e7;
123+
while (left < right) {
124+
int mid = (left + right) >> 1;
125+
if (arriveOnTime(dist, mid, hour)) {
126+
right = mid;
127+
} else {
128+
left = mid + 1;
129+
}
130+
}
131+
return arriveOnTime(dist, left, hour) ? left : -1;
132+
}
133+
134+
bool arriveOnTime(vector<int>& dist, int speed, double hour) {
135+
double res = 0;
136+
for (int i = 0; i < dist.size(); ++i) {
137+
double cost = dist[i] * 1.0 / speed;
138+
res += (i == dist.size() - 1 ? cost : ceil(cost));
139+
}
140+
return res <= hour;
141+
}
142+
};
143+
```
144+
120145
### **JavaScript**
121146

122147
```js
@@ -153,6 +178,36 @@ class Solution {
153178
}
154179
```
155180

181+
### **Go**
182+
183+
```go
184+
func minSpeedOnTime(dist []int, hour float64) int {
185+
n := len(dist)
186+
left, right := 1, int(1e7)
187+
for left < right {
188+
mid := (left + right) >> 1
189+
if arriveOnTime(dist, n, float64(mid), hour) {
190+
right = mid
191+
} else {
192+
left = mid + 1
193+
}
194+
}
195+
if arriveOnTime(dist, n, float64(left), hour) {
196+
return left
197+
}
198+
return -1
199+
}
200+
201+
func arriveOnTime(dist []int, n int, speed, hour float64) bool {
202+
var cost float64
203+
for _, v := range dist[:n-1] {
204+
cost += math.Ceil(float64(v) / speed)
205+
}
206+
cost += float64(dist[n-1]) / speed
207+
return cost <= hour
208+
}
209+
```
210+
156211
### **...**
157212

158213
```

‎solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
class Solution {
2+
public:
3+
int minSpeedOnTime(vector<int>& dist, double hour) {
4+
int left = 1, right = 1e7;
5+
while (left < right) {
6+
int mid = (left + right) >> 1;
7+
if (arriveOnTime(dist, mid, hour)) {
8+
right = mid;
9+
} else {
10+
left = mid + 1;
11+
}
12+
}
13+
return arriveOnTime(dist, left, hour) ? left : -1;
14+
}
15+
16+
bool arriveOnTime(vector<int>& dist, int speed, double hour) {
17+
double res = 0;
18+
for (int i = 0; i < dist.size(); ++i) {
19+
double cost = dist[i] * 1.0 / speed;
20+
res += (i == dist.size() - 1 ? cost : ceil(cost));
21+
}
22+
return res <= hour;
23+
}
24+
};

‎solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
func minSpeedOnTime(dist []int, hour float64) int {
2+
n := len(dist)
3+
left, right := 1, int(1e7)
4+
for left < right {
5+
mid := (left + right) >> 1
6+
if arriveOnTime(dist, n, float64(mid), hour) {
7+
right = mid
8+
} else {
9+
left = mid + 1
10+
}
11+
}
12+
if arriveOnTime(dist, n, float64(left), hour) {
13+
return left
14+
}
15+
return -1
16+
}
17+
18+
func arriveOnTime(dist []int, n int, speed, hour float64) bool {
19+
var cost float64
20+
for _, v := range dist[:n-1] {
21+
cost += math.Ceil(float64(v) / speed)
22+
}
23+
cost += float64(dist[n-1]) / speed
24+
return cost <= hour
25+
}

‎solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java

Lines changed: 7 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,15 @@
11
class Solution {
22
public int minSpeedOnTime(int[] dist, double hour) {
3-
if (dist.length - 1 >= hour) {
4-
return -1;
5-
}
6-
int l = 1, r = 10000000;
7-
while (l < r) {
8-
int m = (l + r) >> 1;
9-
if (arriveOnTime(dist, m, hour)) {
10-
r = m;
3+
int left = 1, right = (int) 1e7;
4+
while (left < right) {
5+
int mid = (left + right) >> 1;
6+
if (arriveOnTime(dist, mid, hour)) {
7+
right = mid;
118
} else {
12-
l = m + 1;
9+
left = mid + 1;
1310
}
1411
}
15-
return l;
12+
return arriveOnTime(dist, left, hour) ? left : -1;
1613
}
1714

1815
private boolean arriveOnTime(int[] dist, int speed, double hour) {

‎solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.py

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -5,13 +5,12 @@ def arrive_on_time(speed):
55
for i, d in enumerate(dist):
66
res += (d / speed) if i == len(dist) - 1 else math.ceil(d / speed)
77
return res <= hour
8-
if len(dist) - 1 >= hour:
9-
return -1
10-
l, r = 1, 10 ** 7
11-
while l < r:
12-
m = (l + r) >> 1
13-
if arrive_on_time(m):
14-
r = m
8+
9+
left, right = 1, 10 ** 7
10+
while left < right:
11+
mid = (left + right) >> 1
12+
if arrive_on_time(mid):
13+
right = mid
1514
else:
16-
l = m + 1
17-
return l
15+
left = mid + 1
16+
return left if arrive_on_time(left) else -1

0 commit comments

Comments
 (0)