rust_algorithms/greedy/
classic.rs

1//! Klassik ochko'z masalalar.
2
3/// Tadbir: boshlanish va tugash vaqti.
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub struct Activity {
6    /// Boshlanish vaqti.
7    pub start: i64,
8    /// Tugash vaqti.
9    pub end: i64,
10}
11
12impl Activity {
13    /// Yangi tadbir.
14    pub fn new(start: i64, end: i64) -> Self {
15        Self { start, end }
16    }
17}
18
19/// Tadbirlarni tanlash: bitta zalda maksimal nechta tadbir o'tkazish mumkin?
20///
21/// **Ochko'z qoida:** **eng erta tugaydigan** tadbirni tanlang. Nima uchun bu ishlaydi?
22/// Chunki erta tugagan tadbir keyingilar uchun eng ko'p joy qoldiradi.
23///
24/// - **Time:** O(n log n) (tartiblash), **Space:** O(n).
25///
26/// Qaytadi: tanlangan tadbirlarning **asl** indekslari.
27///
28/// # Misol
29/// ```
30/// use rust_algorithms::greedy::{activity_selection, Activity};
31///
32/// let tadbirlar = vec![
33///     Activity::new(1, 4),
34///     Activity::new(3, 5),
35///     Activity::new(0, 6),
36///     Activity::new(5, 7),
37///     Activity::new(8, 9),
38///     Activity::new(5, 9),
39/// ];
40/// let tanlangan = activity_selection(&tadbirlar);
41/// assert_eq!(tanlangan, vec![0, 3, 4]); // (1,4), (5,7), (8,9)
42/// ```
43pub fn activity_selection(activities: &[Activity]) -> Vec<usize> {
44    let mut tartib: Vec<usize> = (0..activities.len()).collect();
45    tartib.sort_by_key(|&i| activities[i].end);
46
47    let mut natija = Vec::new();
48    let mut oxirgi = i64::MIN;
49    for i in tartib {
50        if activities[i].start >= oxirgi {
51            natija.push(i);
52            oxirgi = activities[i].end;
53        }
54    }
55    natija
56}
57
58/// Xaltaga solinadigan buyum: qiymati va og'irligi.
59#[derive(Debug, Clone, Copy)]
60pub struct Item {
61    /// Buyum qiymati.
62    pub value: f64,
63    /// Buyum og'irligi.
64    pub weight: f64,
65}
66
67impl Item {
68    /// Yangi buyum.
69    pub fn new(value: f64, weight: f64) -> Self {
70        Self { value, weight }
71    }
72}
73
74/// **Bo'linadigan xalta masalasi** (fractional knapsack).
75///
76/// Buyumlarni bo'lish mumkin (masalan, un, shakar, oltin kukuni).
77/// Sig'imi `capacity` bo'lgan xaltaga maksimal **qiymat** joylang.
78///
79/// **Ochko'z qoida:** `qiymat / og'irlik` nisbati eng katta buyumdan boshlang.
80/// Bu yerda ochko'zlik **isbotlangan optimal** — chunki buyumni bo'lish mumkin.
81///
82/// - **Time:** O(n log n), **Space:** O(n).
83///
84/// # Misol
85/// ```
86/// use rust_algorithms::greedy::{fractional_knapsack, Item};
87///
88/// let buyumlar = vec![
89///     Item::new(60.0, 10.0),  // nisbat 6.0
90///     Item::new(100.0, 20.0), // nisbat 5.0
91///     Item::new(120.0, 30.0), // nisbat 4.0
92/// ];
93/// let qiymat = fractional_knapsack(&buyumlar, 50.0);
94/// assert!((qiymat - 240.0).abs() < 1e-9); // 60 + 100 + 120*(20/30)
95/// ```
96pub fn fractional_knapsack(items: &[Item], capacity: f64) -> f64 {
97    let mut tartib: Vec<&Item> = items.iter().collect();
98    tartib.sort_by(|a, b| {
99        let na = a.value / a.weight;
100        let nb = b.value / b.weight;
101        nb.partial_cmp(&na).unwrap_or(std::cmp::Ordering::Equal)
102    });
103
104    let mut qolgan = capacity;
105    let mut jami = 0.0;
106    for it in tartib {
107        if qolgan <= 0.0 {
108            break;
109        }
110        if it.weight <= qolgan {
111            jami += it.value; // butunligicha olamiz
112            qolgan -= it.weight;
113        } else {
114            jami += it.value * (qolgan / it.weight); // qismini olamiz
115            qolgan = 0.0;
116        }
117    }
118    jami
119}
120
121/// Qaytim berish (coin change) — **ochko'z** yondashuv.
122///
123/// Har safar eng katta sig'adigan tangani olamiz.
124///
125/// > ⚠️ **Diqqat:** bu **har doim ham optimal emas!** U faqat "kanonik" tanga
126/// > tizimlarida to'g'ri ishlaydi (masalan, 1, 5, 10, 25, 50, 100).
127/// >
128/// > Qarshi misol: tangalar `[1, 3, 4]`, summa `6`.
129/// > Ochko'z: 4 + 1 + 1 = **3 ta** tanga. Optimal: 3 + 3 = **2 ta**.
130/// > To'g'ri javob uchun [`crate::dp::coin_change_min`] (DP) ni ishlating.
131///
132/// - **Time:** O(n log n + summa/eng_kichik_tanga).
133///
134/// # Misol
135/// ```
136/// use rust_algorithms::greedy::coin_change_greedy;
137///
138/// // kanonik tizim — to'g'ri ishlaydi
139/// assert_eq!(coin_change_greedy(&[1, 5, 10, 25], 63), Some(vec![25, 25, 10, 1, 1, 1]));
140///
141/// // kanonik bo'lmagan tizim — optimal emas!
142/// assert_eq!(coin_change_greedy(&[1, 3, 4], 6), Some(vec![4, 1, 1])); // 3 ta, optimal 2 ta
143///
144/// assert_eq!(coin_change_greedy(&[5, 10], 3), None); // yechim yo'q
145/// ```
146pub fn coin_change_greedy(coins: &[u64], amount: u64) -> Option<Vec<u64>> {
147    let mut tangalar: Vec<u64> = coins.iter().copied().filter(|&c| c > 0).collect();
148    tangalar.sort_unstable_by(|a, b| b.cmp(a)); // kattadan kichikka
149
150    let mut qolgan = amount;
151    let mut natija = Vec::new();
152    for c in tangalar {
153        while qolgan >= c {
154            qolgan -= c;
155            natija.push(c);
156        }
157        if qolgan == 0 {
158            break;
159        }
160    }
161    if qolgan == 0 {
162        Some(natija)
163    } else {
164        None
165    }
166}
167
168/// Minimal perron soni: bir vaqtning o'zida stansiyada eng ko'pi bilan nechta
169/// poyezd turadi?
170///
171/// **Ochko'z qoida:** kelish va ketish vaqtlarini alohida tartiblab, ikkita
172/// ko'rsatkich bilan yuramiz. Kelish ketishdan oldin bo'lsa — yangi perron kerak.
173///
174/// - **Time:** O(n log n).
175///
176/// # Misol
177/// ```
178/// use rust_algorithms::greedy::min_platforms;
179///
180/// let kelish = [900, 940, 950, 1100, 1500, 1800];
181/// let ketish = [910, 1200, 1120, 1130, 1900, 2000];
182/// assert_eq!(min_platforms(&kelish, &ketish), 3);
183/// ```
184pub fn min_platforms(arrivals: &[i64], departures: &[i64]) -> usize {
185    assert_eq!(arrivals.len(), departures.len());
186    let mut kelish = arrivals.to_vec();
187    let mut ketish = departures.to_vec();
188    kelish.sort_unstable();
189    ketish.sort_unstable();
190
191    let (mut i, mut j) = (0usize, 0usize);
192    let (mut hozir, mut maksimum) = (0usize, 0usize);
193
194    while i < kelish.len() {
195        if kelish[i] <= ketish[j] {
196            hozir += 1;
197            maksimum = maksimum.max(hozir);
198            i += 1;
199        } else {
200            hozir -= 1;
201            j += 1;
202        }
203    }
204    maksimum
205}
206
207#[cfg(test)]
208mod tests {
209    use super::*;
210
211    #[test]
212    fn tadbirlar_kesishmaydi() {
213        let a = vec![
214            Activity::new(1, 3),
215            Activity::new(2, 5),
216            Activity::new(4, 7),
217            Activity::new(6, 8),
218        ];
219        let tanlangan = activity_selection(&a);
220        assert_eq!(tanlangan, vec![0, 2]);
221        // tanlanganlar kesishmasligini tekshiramiz
222        for w in tanlangan.windows(2) {
223            assert!(a[w[0]].end <= a[w[1]].start);
224        }
225    }
226
227    #[test]
228    fn bosh_royxat() {
229        assert!(activity_selection(&[]).is_empty());
230        assert_eq!(fractional_knapsack(&[], 10.0), 0.0);
231    }
232
233    #[test]
234    fn xalta_sigimi_yetarli_bolsa_hammasi() {
235        let items = vec![Item::new(10.0, 1.0), Item::new(20.0, 2.0)];
236        assert!((fractional_knapsack(&items, 100.0) - 30.0).abs() < 1e-9);
237    }
238
239    #[test]
240    fn qaytim_summasi_togri() {
241        for summa in 1u64..200 {
242            let t = coin_change_greedy(&[1, 5, 10, 25], summa).unwrap();
243            assert_eq!(t.iter().sum::<u64>(), summa);
244        }
245        assert_eq!(coin_change_greedy(&[2], 5), None);
246        assert_eq!(coin_change_greedy(&[1], 0), Some(vec![]));
247    }
248
249    #[test]
250    fn perronlar() {
251        assert_eq!(min_platforms(&[900, 1100, 1235], &[1000, 1200, 1240]), 1);
252        assert_eq!(min_platforms(&[900, 910], &[1000, 1010]), 2);
253    }
254}
rust_algorithms/greedy/classic.rs

rust_algorithms/greedy/
classic.rs
