Π‘ΡΡΠ»ΠΊΠ° Π½Π° Π·Π°Π΄Π°ΡΡ β 2594. Minimum Time to Repair Cars.
β ΠΠΏΠΈΡΠ°Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ
ΠΠ°Π½ΠΎ:
ranks
β ΡΠΏΠΈΡΠΎΠΊ ΡΠ°Π½Π³ΠΎΠ² ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠΎΠ².
- ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊ Ρ ΡΠ°Π½Π³ΠΎΠΌ
r
ΠΌΠΎΠΆΠ΅Ρ ΠΏΠΎΡΠΈΠ½ΠΈΡΡ n
ΠΌΠ°ΡΠΈΠ½ Π·Π° r * nΒ²
ΠΌΠΈΠ½ΡΡ.
cars
β ΠΎΠ±ΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΌΠ°ΡΠΈΠ½, ΠΎΠΆΠΈΠ΄Π°ΡΡΠΈΡ
ΡΠ΅ΠΌΠΎΠ½ΡΠ°.
ΠΡΠΆΠ½ΠΎ Π½Π°ΠΉΡΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ, Π·Π° ΠΊΠΎΡΠΎΡΠΎΠ΅ Π²ΡΠ΅ ΠΌΠ°ΡΠΈΠ½Ρ Π±ΡΠ΄ΡΡ ΠΎΡΡΠ΅ΠΌΠΎΠ½ΡΠΈΡΠΎΠ²Π°Π½Ρ.
ΠΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ, ΡΡΠΎ Π²ΡΠ΅ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠΈ ΡΠ°Π±ΠΎΡΠ°ΡΡ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ.
π‘ ΠΠ΄Π΅Ρ
ΠΠ΅Ρ
Π°Π½ΠΈΠΊΠΈ Ρ ΠΌΠ΅Π½ΡΡΠΈΠΌ ΡΠ°Π½Π³ΠΎΠΌ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π±ΡΡΡΡΠ΅Π΅.
ΠΡΠΎΠΈΠ·Π²Π΅Π΄ΡΠΌ ΠΏΠ΅ΡΠ²ΠΈΡΠ½ΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΌΠ°ΡΠΈΠ½, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ ΠΎΠ±ΡΠ°ΡΠ½ΡΠΉ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΠΉ ΠΊΠΎΡΠ΅Π½Ρ ΡΠ°Π½Π³Π° ΠΊΠ°ΠΊ Π²Π΅Ρ, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΠΈΠΉ Π΄ΠΎΠ»Ρ ΠΌΠ°ΡΠΈΠ½, ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΡΡ
ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΡ.
ΠΠ΄Π½Π°ΠΊΠΎ ΡΡΠΎ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Π½Π΅ ΠΏΠΎΠΊΡΡΠ²Π°Π΅Ρ Π²ΡΠ΅ ΠΌΠ°ΡΠΈΠ½Ρ. ΠΠ»Ρ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΎΡΡΠ°Π²ΡΠΈΡ
ΡΡ ΠΌΠ°ΡΠΈΠ½ ΠΌΡ ΠΏΠΎΡΡΠΈΡΠ°Π΅ΠΌ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠ° ΠΎΡΠ΅Π½ΠΊΡ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π΅Π³ΠΎ ΡΠ°Π±ΠΎΡΡ, Π΅ΡΠ»ΠΈ Π²Π·ΡΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΡ
ΠΌΠ°ΡΠΈΠ½ (ΡΠ΅ΠΌ Π±ΠΎΠ»ΡΡΠ΅, ΡΠ΅ΠΌ Π±ΠΎΠ»ΡΡΠ΅ Π²Π΅Ρ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠ°). ΠΠΎΡΠ»Π΅ ΠΎΡΡΠ°ΡΡΡΡ Π»ΠΈΡΡ Π²ΡΠ±ΡΠ°ΡΡ k
-ΠΎΠ΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΡΡΠ΅Π΄ΠΈ ΠΏΠΎΡΡΠΈΡΠ°Π½Π½ΡΡ
Π²ΡΠ΅ΠΌΡΠ½ Ρ ΠΏΠΎΠΌΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Β«QuickSelectΒ» (Π»ΡΠ±Π΅Π·Π½ΠΎ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π² ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΠΎΠΉ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ΅ Rust
).
π ΠΠ΅ΡΠ°Π»ΠΈ ΠΏΠΎΠ΄Ρ
ΠΎΠ΄Π°
1οΈβ£ ΠΡΡΡΡΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ β Π²ΡΡΠΈΡΠ»ΡΠ΅ΠΌ Π²Π΅Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠ° ΠΈ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΠΌ ΠΌΠ°ΡΠΈΠ½Ρ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎ.
2οΈβ£ ΠΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ ΠΎΡΠ΅Π½ΠΊΠΈ β Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠ° ΠΏΡΠ΅Π΄Π²ΡΡΠΈΡΠ»ΡΠ΅ΠΌ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠ΅ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π²ΡΠ΅ΠΌΠ΅Π½Π° ΡΠ΅ΠΌΠΎΠ½ΡΠ° (ΡΠΎΠ³Π»Π°ΡΠ½ΠΎ Π²Π΅ΡΡ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠ°).
3οΈβ£ ΠΡΠ±ΠΎΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ β ΠΏΡΠΈΠΌΠ΅Π½ΡΠ΅ΠΌ ΠΌΠ΅ΡΠΎΠ΄ ΠΈΠ· ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΠΎΠΉ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ select_nth_unstable
, ΡΡΠΎΠ±Ρ Π½Π°ΠΉΡΠΈ Π½Π°ΠΈΠ»ΡΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ ΡΠ΅ΠΌΠΎΠ½ΡΠ° Π½Π΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»ΡΠ½Π½ΡΡ
ΠΈΠ·Π½Π°ΡΠ°Π»ΡΠ½ΠΎ ΠΌΠ°ΡΠΈΠ½.
β³ ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ°
- ΠΡΠ΅ΠΌΡ: _
O(N)
- ΠΠ΅ΡΠ²ΠΈΡΠ½ΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅:
O(N)
- Π Π°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΎΡΡΠ°Π²ΡΠΈΡ
ΡΡ:
O(N)
β select_nth_unstable
.
- ΠΠ°ΠΌΡΡΡ:
O(N)
- Π₯ΡΠ°Π½Π΅Π½ΠΈΠ΅ Π²ΡΠ΅ΠΌΡΠ½ Π΄Π»Ρ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΡ
Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΡ
ΠΌΠ°ΡΠΈΠ½ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠ°.
ΠΠ°ΠΌΠ΅ΡΠ°Π½ΠΈΠ΅
Π£ ΠΌΠ΅Π½Ρ Π½Π΅Ρ ΡΡΡΠΊΠΎΠ³ΠΎ ΠΏΠ»Π°Π½Π° Π΄ΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²Π° ΠΊΠΎΡΡΠ΅ΠΊΡΠ½ΠΎΡΡΠΈ ΡΠ²ΡΠΈΡΡΠΈΠΊΠΈ Ρ ΠΏΡΠ΅Π΄ΡΠ°ΡΡΡΡΠΎΠΌ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡΠ΅Π»ΡΠ½ΡΡ
ΠΌΠ°ΡΠΈΠ½ Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· ΠΌΠ΅Ρ
Π°Π½ΠΈΠΊΠΎΠ². ΠΠΎ Π½Π° Π²ΡΠ΅Ρ
ΡΠ°Π·ΡΠΌΠ½ΡΡ
ΠΌΠΎΠΈΡ
ΡΠ΅ΡΡΠ°Ρ
ΠΈ ΡΠ΅ΡΡΠ°Ρ
Ρ LeetCode ΡΠ²ΡΠΈΡΡΠΈΠΊΠ° ΡΡΠΏΠ΅ΡΠ½ΠΎ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ!
π ΠΡΡ
ΠΎΠ΄Π½ΡΠΉ ΠΊΠΎΠ΄
impl Solution {
pub fn repair_cars(ranks: Vec<i32>, mut cars: i32) -> i64 {
// Normalization factor to weight mechanics by inverse square root of ranks.
let weights_normalize: f64 = 1.0 / ranks.iter()
.map(|&rank| (1.0 / rank as f64).sqrt())
.sum::<f64>();
let total_cars = cars as f64;
let total_mechanics = ranks.len() as f64;
let mut max_time = 0i64;
let mut next_times = Vec::new();
// Quickly assign cars based on mechanic ranks (weighted by inverse square root of rank).
for &rank in &ranks {
let weight = (1.0 / rank as f64).sqrt() * weights_normalize;
let assigned = (total_cars * weight) as i32;
cars -= assigned;
let time = Self::repair_time(rank, assigned);
max_time = max_time.max(time);
// Determine the number of additional cars dynamically based on weight
let additional_cars = (total_mechanics * weight).ceil() as i32; // Adjusted heuristic for next times
for offset in 1..=additional_cars {
next_times.push(Self::repair_time(rank, assigned + offset));
}
}
// Determine final max time considering remaining cars
if cars > 0 {
let (_, nth_time, _) = next_times.select_nth_unstable(cars as usize - 1);
max_time = max_time.max(*nth_time);
}
max_time
}
/// Calculates repair time for a given mechanic rank and number of cars
fn repair_time(rank: i32, cars: i32) -> i64 {
rank as i64 * (cars as i64).pow(2)
}
}
Tags: #rust #algorithms #optimization #heuristics