greedy/
lib.rs

1//! # Rust Greedy
2
3#![feature(test)]
4
5extern crate test;
6
7/// 135h Candy
8struct Sol135 {}
9
10impl Sol135 {
11    pub fn candy(ratings: Vec<i32>) -> i32 {
12        let mut candies = vec![1; ratings.len()];
13
14        for i in 0..candies.len() - 1 {
15            if ratings[i] < ratings[i + 1] {
16                candies[i + 1] = candies[i + 1].max(candies[i] + 1);
17            }
18        }
19
20        for i in (1..candies.len()).rev() {
21            if ratings[i - 1] > ratings[i] {
22                candies[i - 1] = candies[i - 1].max(candies[i] + 1);
23            }
24        }
25
26        println!("-> {candies:?}");
27
28        candies.iter().sum()
29    }
30}
31
32/// 630h Course Schedule III
33struct Sol630 {}
34impl Sol630 {
35    pub fn schedule_course(courses: Vec<Vec<i32>>) -> i32 {
36        use std::collections::BinaryHeap;
37
38        let mut courses = courses;
39        courses.sort_by_key(|course| course[1]);
40
41        let mut start = 0;
42        let mut pq = BinaryHeap::new();
43        for course in courses {
44            start += course[0];
45            pq.push(course[0]);
46
47            if start > course[1]
48                && let Some(days) = pq.pop()
49            {
50                start -= days;
51            }
52        }
53
54        pq.len() as _
55    }
56}
57
58/// 781m Rabbits in Forest
59struct Sol781;
60
61impl Sol781 {
62    /// 1 <= N <= 1000, 0 <= N_i < 10000
63    pub fn num_rabbits(answers: Vec<i32>) -> i32 {
64        let freq = answers.iter().fold([0; 1000], |mut freq, &f| {
65            freq[f as usize] += 1;
66            freq
67        });
68
69        freq.iter()
70            .enumerate()
71            .map(|(n, f)| (n as i32 + 1, f))
72            .fold(0, |count, (n, f)| count + (f + n - 1) / n * n)
73    }
74}
75
76/// 1007m Minimum Domino Rotations For Equal Row
77struct Sol1007;
78
79impl Sol1007 {
80    pub fn min_domino_rotations(tops: Vec<i32>, bottoms: Vec<i32>) -> i32 {
81        let mut r = i32::MAX;
82
83        'LOOP: for n in 1..=6 {
84            let mut top = 0;
85            let mut bottom = 0;
86
87            for (&t, &b) in tops.iter().zip(bottoms.iter()) {
88                if t != n && b != n {
89                    continue 'LOOP;
90                }
91
92                if t != n {
93                    top += 1;
94                }
95                if b != n {
96                    bottom += 1;
97                }
98            }
99
100            r = r.min(top.min(bottom));
101        }
102
103        if r < i32::MAX {
104            return r;
105        }
106        -1
107    }
108}
109
110/// 1717m Maximum Score From Removing Substrings
111struct Sol1717 {}
112
113impl Sol1717 {
114    pub fn maximum_gain(s: String, mut x: i32, mut y: i32) -> i32 {
115        let (mut a, mut b) = ('a', 'b');
116        if x < y {
117            (a, b) = ('b', 'a');
118            (x, y) = (y, x);
119        }
120
121        let mut s: Vec<_> = s.chars().collect();
122
123        let mut gain = 0;
124        for g in [x, y] {
125            let mut stack = vec![];
126            gain += s.iter().fold(0, |mut gain, &chr| {
127                if let Some(&prv) = stack.last() {
128                    if prv == a && chr == b {
129                        stack.pop();
130                        gain += g;
131                    } else {
132                        stack.push(chr);
133                    }
134                } else {
135                    stack.push(chr);
136                }
137
138                gain
139            });
140
141            s = stack;
142            (a, b) = (b, a);
143        }
144
145        gain
146    }
147}
148
149/// 1733m Minimum Number of People to Teach
150struct Sol1733 {}
151
152impl Sol1733 {
153    pub fn minimum_teachings(n: i32, languages: Vec<Vec<i32>>, friendships: Vec<Vec<i32>>) -> i32 {
154        use std::collections::HashSet;
155
156        let mut fls: Vec<HashSet<i32>> = vec![];
157        for langs in languages.iter() {
158            fls.push(langs.iter().copied().collect::<HashSet<_>>());
159        }
160        println!("-> Friends Language Set Vector: {fls:?}");
161
162        let filter_cache: HashSet<(usize, usize)> = friendships
163            .iter()
164            .map(|v| (v[0] as usize - 1, v[1] as usize - 1))
165            .filter(|&(x, y)| fls[x].intersection(&fls[y]).count() == 0)
166            .collect();
167        println!("-> Friends With No Common Language (0-Index): {filter_cache:?}");
168
169        (1..=n)
170            .map(|lang| {
171                friendships
172                    .iter()
173                    .map(|v| (v[0] as usize - 1, v[1] as usize - 1))
174                    .filter(|&(u, v)| filter_cache.contains(&(u, v)))
175                    .flat_map(|(u, v)| {
176                        let mut learners = vec![];
177                        if !fls[u].contains(&lang) {
178                            learners.push(u);
179                        }
180                        if !fls[v].contains(&lang) {
181                            learners.push(v);
182                        }
183
184                        learners
185                    })
186                    .collect::<HashSet<_>>()
187                    .len()
188            })
189            .min()
190            .unwrap_or(0) as _
191    }
192}
193
194/// 1353m Maximum Number of Events That Can Be Attended
195struct Sol1353 {}
196
197impl Sol1353 {
198    /// 1 <= N, Start_i, End_i <= 10^5
199    pub fn max_events(mut events: Vec<Vec<i32>>) -> i32 {
200        use std::cmp::Reverse;
201        use std::collections::BinaryHeap;
202
203        let final_day = events.iter().map(|v| v[1]).max().unwrap_or(0);
204
205        events.sort_by_key(|v| v[0]);
206        println!("-> {events:?}");
207
208        let mut pq = BinaryHeap::new();
209
210        let mut count = 0;
211        let mut p = 0;
212        for day in 1..=final_day {
213            while p < events.len() && events[p][0] <= day {
214                pq.push(Reverse(events[p][1]));
215                p += 1;
216            }
217
218            while let Some(&Reverse(end)) = pq.peek() {
219                if end < day {
220                    pq.pop();
221                    continue;
222                }
223                break;
224            }
225
226            if let Some(Reverse(_)) = pq.pop() {
227                count += 1;
228            }
229        }
230
231        count
232    }
233}
234
235/// 2014h Longest Subsequence Repeated K Times
236struct Sol2014 {}
237
238impl Sol2014 {
239    pub fn longest_subsequence_repeated_k(s: String, k: i32) -> String {
240        use std::collections::{HashMap, VecDeque};
241
242        let mut freqs = HashMap::new();
243        for chr in s.chars() {
244            *freqs.entry(chr).or_insert(0) += 1;
245        }
246        println!("-> {freqs:?}");
247
248        let mut chrs = vec![];
249        for chr in ('a'..='z').rev() {
250            if let Some(&f) = freqs.get(&chr)
251                && f >= k
252            {
253                chrs.push(chr);
254            }
255        }
256        println!("-> {chrs:?}");
257
258        let mut queue = VecDeque::new();
259        for chr in chrs.iter() {
260            queue.push_back(chr.to_string());
261        }
262
263        let check = |p: &str| {
264            let p: Vec<_> = p.chars().collect();
265
266            let (mut fcount, mut i) = (0, 0);
267            for chr in s.chars() {
268                if chr == p[i] {
269                    i += 1;
270                    if i == p.len() {
271                        fcount += 1;
272                        if fcount == k {
273                            return true;
274                        }
275                        i = 0;
276                    }
277                }
278            }
279
280            false
281        };
282
283        let mut lsr = String::new();
284        while let Some(cur) = queue.pop_front() {
285            println!("-> {cur:?}   {queue:?}");
286
287            if cur.len() > lsr.len() {
288                lsr = cur.clone();
289            }
290
291            for &chr in chrs.iter() {
292                let cur = cur.clone() + &chr.to_string();
293                if check(&cur) {
294                    queue.push_back(cur);
295                }
296            }
297        }
298
299        lsr
300    }
301}
302
303/// 2131m Longest Palindrome by Concatenating Two Letter Words
304struct Sol2131 {}
305
306impl Sol2131 {
307    pub fn longest_palindrome(words: Vec<String>) -> i32 {
308        use std::collections::HashMap;
309
310        let mut fwords = HashMap::new();
311        for word in &words {
312            fwords.entry(word).and_modify(|f| *f += 1).or_insert(1);
313        }
314
315        println!("-> {fwords:?}");
316
317        let mut extra = 0;
318        fwords.keys().fold(0, |length, &w| match fwords.get(&w) {
319            Some(&f) => {
320                let chrs: Vec<_> = w.chars().collect();
321                length
322                    + match chrs
323                        .iter()
324                        .zip(chrs.iter().rev())
325                        .all(|(chr1, chr2)| chr1 == chr2)
326                    {
327                        true => match f & 1 {
328                            1 => {
329                                extra = 2;
330                                f - 1
331                            }
332                            _ => f,
333                        },
334                        _ => match fwords.get(&String::from_iter(chrs.iter().rev())) {
335                            Some(&p) => f.min(p),
336                            _ => 0,
337                        },
338                    }
339            }
340            _ => length,
341        }) * 2
342            + extra
343    }
344}
345
346/// 2294m Partition Array Such That Maximum Difference Is K
347struct Sol2294 {}
348
349impl Sol2294 {
350    /// 1 <= N, k <= 10^5
351    pub fn partition_array(mut nums: Vec<i32>, k: i32) -> i32 {
352        nums.sort_unstable();
353
354        let mut start = nums[0];
355        nums[1..].iter().fold(0, |r, &n| {
356            if n - start > k {
357                start = n;
358                r + 1
359            } else {
360                r
361            }
362        }) + 1
363    }
364}
365
366/// 2311m Longest Binary Subsequence Less Than or Equal to K
367struct Sol2311 {}
368
369impl Sol2311 {
370    pub fn longest_subsequence(s: String, k: i32) -> i32 {
371        let mut sval = 0;
372        let bits = k.ilog2() as usize + 1;
373
374        s.chars()
375            .rev()
376            .enumerate()
377            .fold(0, |mut longest, (i, chr)| {
378                match chr {
379                    '1' => {
380                        if i < bits && sval + (1 << i) <= k {
381                            sval += 1 << i;
382                            longest += 1
383                        }
384                    }
385                    _ => longest += 1,
386                }
387
388                longest
389            })
390    }
391}
392
393/// 2434m Using a Robot to Print the Lexicographically Smallest String
394struct Sol2434 {}
395
396impl Sol2434 {
397    pub fn robot_with_string(s: String) -> String {
398        use std::collections::HashMap;
399
400        let mut freqs: HashMap<char, usize> = HashMap::new();
401        for chr in s.chars() {
402            freqs.entry(chr).and_modify(|f| *f += 1).or_insert(1);
403        }
404
405        let mut prints = vec![];
406
407        let mut stack = vec![];
408        for chr in s.chars() {
409            stack.push(chr);
410            freqs.entry(chr).and_modify(|f| *f -= 1);
411
412            if let Some(marker) = ('a'..='z').find(|chr| freqs.contains_key(chr) && freqs[chr] != 0)
413            {
414                while let Some(&chr) = stack.last()
415                    && chr <= marker
416                {
417                    prints.push(chr);
418                    stack.pop();
419                }
420            }
421        }
422
423        while let Some(chr) = stack.pop() {
424            prints.push(chr);
425        }
426
427        prints.iter().collect()
428    }
429}
430
431/// 2900 Longest Unequal Adjacent Groups Subsequence I
432struct Sol2900;
433
434impl Sol2900 {
435    /// 1 <= |words, groups| <= 100
436    pub fn get_longest_subsequence(mut words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
437        words.reverse();
438        groups
439            .iter()
440            .skip(1)
441            .fold(
442                (vec![words.pop().unwrap()], groups[0]),
443                |(mut ls, cur_group), &g| {
444                    if cur_group == g {
445                        words.pop();
446                        (ls, g)
447                    } else {
448                        ls.push(words.pop().unwrap());
449                        (ls, g)
450                    }
451                },
452            )
453            .0
454    }
455}
456
457/// 2918m Minimum Equal Sum of Two Arrays After Replacing Zeros
458struct Sol2918;
459
460impl Sol2918 {
461    pub fn min_sum(nums1: Vec<i32>, nums2: Vec<i32>) -> i64 {
462        let folder = |(sum, zeros), n| match n == 0 {
463            true => (sum + 1, zeros + 1),
464            _ => (sum + n as i64, zeros),
465        };
466
467        let (sum1, zeros1) = nums1.into_iter().fold((0, 0), folder);
468        let (sum2, zeros2) = nums2.into_iter().fold((0, 0), folder);
469
470        if sum1 > sum2 && zeros2 == 0 || sum2 > sum1 && zeros1 == 0 {
471            return -1;
472        }
473        sum1.max(sum2)
474    }
475}
476
477/// 3170m Lexicographically Minimum String After Removing Stars
478struct Sol3170 {}
479
480impl Sol3170 {
481    pub fn clear_stars(s: String) -> String {
482        use std::cmp::Reverse;
483        use std::collections::BinaryHeap;
484
485        let mut buffer: Vec<_> = s.chars().collect();
486        let mut pq = BinaryHeap::new();
487
488        for (i, chr) in s.chars().enumerate() {
489            println!("-> {pq:?}");
490            match chr {
491                '*' => {
492                    if let Some((_, i)) = pq.pop() {
493                        buffer[i] = '*';
494                    }
495                }
496                _ => pq.push((Reverse(chr), i)),
497            }
498        }
499
500        println!("-> {buffer:?}");
501
502        buffer.iter().filter(|&chr| chr != &'*').collect()
503    }
504}
505
506/// 3439m Reschedule Meetings for Maximum Free Time I
507struct Sol3439 {}
508
509impl Sol3439 {
510    pub fn max_free_time(event_time: i32, k: i32, start_time: Vec<i32>, end_time: Vec<i32>) -> i32 {
511        let n = start_time.len() & end_time.len();
512
513        let mut len_pfx = vec![0; n + 1];
514        for i in 0..n {
515            len_pfx[i + 1] = len_pfx[i] + end_time[i] - start_time[i];
516        }
517
518        let k = k as usize;
519        (k - 1..n).fold(0, |xfree, p| {
520            let r = if p == n - 1 {
521                event_time
522            } else {
523                start_time[p + 1]
524            };
525            let l = if p == k - 1 { 0 } else { end_time[p - k] };
526
527            xfree.max(r - l - (len_pfx[p + 1] - len_pfx[p + 1 - k]))
528        }) as _
529    }
530}
531
532/// 3440m Reschedule Meetings for Maximum Free Time II
533struct Sol3440 {}
534impl Sol3440 {
535    pub fn max_free_time(event_time: i32, start_time: Vec<i32>, end_time: Vec<i32>) -> i32 {
536        let n = start_time.len() & end_time.len();
537
538        let mut fits = vec![false; n];
539        let (mut lgap, mut rgap) = (0, 0);
540        for i in 0..n {
541            if end_time[i] - start_time[i] <= lgap {
542                fits[i] = true;
543            }
544            lgap = lgap.max(start_time[i] - if i == 0 { 0 } else { end_time[i - 1] });
545
546            let j = n - 1 - i;
547            if end_time[j] - start_time[j] <= rgap {
548                fits[j] = true;
549            }
550            rgap = rgap.max(
551                if j == n - 1 {
552                    event_time
553                } else {
554                    start_time[j + 1]
555                } - end_time[j],
556            );
557        }
558
559        (0..n).fold(0, |xfree, i| {
560            let l = if i == 0 { 0 } else { end_time[i - 1] };
561            let r = if i == n - 1 {
562                event_time
563            } else {
564                start_time[i + 1]
565            };
566
567            if fits[i] {
568                xfree.max(r - l)
569            } else {
570                xfree.max(r - l - (end_time[i] - start_time[i]))
571            }
572        }) as _
573    }
574}
575
576#[cfg(test)]
577mod tests;
greedy/lib.rs

greedy/
lib.rs
