thảo luận Leetcode mỗi ngày

use std::collections::*;
use std::cmp::*;

impl Solution {
    pub fn min_days(bloom_day: Vec<i32>, m: i32, k: i32) -> i32 {
        let n = bloom_day.len();

        let bloom_day_map: HashSet<i32> = bloom_day.iter().map(|&day| day).collect();
        let mut bloom_days: Vec<i32> = bloom_day_map.into_iter().collect();
        bloom_days.sort_unstable();

        let min_day_result =
            bloom_days.binary_search_by(|day| {
                let mut bouquet_count = 0;
                let mut adj_count = 0;

                for i in 0..n {
                    if &bloom_day[i] <= day {
                        adj_count += 1;
                    } else {
                        adj_count = 0;
                    }

                    if (adj_count == k) {
                        bouquet_count += 1;
                        adj_count = 0;
                    }
                }

                // altered binary search to find smallest `i` such that `bloom_day[i] >= m`
                match bouquet_count.cmp(&m) {
                    Ordering::Equal => Ordering::Greater,
                    other => other
                }
            });

        match min_day_result {
            Ok(min_day) => bloom_days[min_day], // should never happen
            Err(min_day) => {
                if min_day < bloom_days.len() {
                    bloom_days[min_day]
                } else {
                    -1
                }
            }
        }
    }
}

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if(n<(long)m*k) return -1;
        int l = 1;
        int r = 0;
        for(int day:bloomDay){
            r = Math.max(r, day);
        }
        while(l<r){
            int mid = l+(r-l)/2;
            if(condition(bloomDay, mid,m,k)){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        return l;
    }
    boolean condition(int[] bloomDay, int day, int m,int k){
        int cnt=0;
        for(int i=0;i<bloomDay.length;i++){
            if(bloomDay[i]<=day){
                cnt++;
            }
            else{
                cnt=0;
            }
            if(cnt>=k){
                m--;
                cnt=0;
            }
            if(m<=0) return true;
        }
        return false;
    }
}

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def isGood(candidate):
            curBouquetSize = 0
            bouquetCount = 0
            for day in bloomDay:
                if day > candidate:
                    curBouquetSize = 0
                    continue
                
                curBouquetSize += 1
                if curBouquetSize == k:
                    bouquetCount += 1
                    curBouquetSize = 0
                    if bouquetCount == m:
                        return True

            return False
        
        if m * k > len(bloomDay):
            return -1
        lo, hi = min(bloomDay), max(bloomDay)
        return bisect.bisect_left(range(lo, hi + 1), x=True, key=isGood) + lo

use std::cmp::*;
use std::ops::*;

trait BinarySearch<F, Idx>
where
    F: FnMut(Idx) -> Ordering
{
    fn binary_search_by(&self, f: F) -> Result<Idx, Idx>;

    fn binary_search_min_by(&self, f: F) -> Idx;

    fn binary_search_max_by(&self, f: F) -> Idx;
}

macro_rules! impl_binary_search_for_range {
    ($($t:ty)*) => ($(
        impl<F> BinarySearch<F, $t> for Range<$t>
        where F: FnMut($t) -> Ordering,
        {
            fn binary_search_by(&self, mut f: F) -> Result<$t, $t> {
                let mut left = self.start;
                let mut right = self.end;

                while left < right {
                    let middle = left + (right - left) / 2;

                    match f(middle) {
                        Ordering::Equal => return Ok(middle),
                        Ordering::Less => left = middle + 1,
                        Ordering::Greater => right = middle
                    }
                }

                Err(left)
            }

            fn binary_search_min_by(&self, mut f: F) -> $t {
                let search_result =
                    Self::binary_search_by(&self, |index| {
                        match f(index) {
                            Ordering::Equal => Ordering::Greater,
                            other => other
                        }
                    });

                search_result.unwrap_or_else(|i| i)
            }

            fn binary_search_max_by(&self, mut f: F) -> $t {
                let search_result =
                    Self::binary_search_by(&self, |index| {
                        match f(index) {
                            Ordering::Equal => Ordering::Less,
                            other => other
                        }
                    });

                search_result.unwrap_or_else(|i| i)
            }
        }
    )*)
}

impl_binary_search_for_range!{ i8 u8 i16 u16 i32 u32 i64 u64 isize usize }

impl Solution {
    pub fn min_days(bloom_day: Vec<i32>, m: i32, k: i32) -> i32 {
        let (min_day, max_day) =
            bloom_day.iter().
                fold((i32::MAX, i32::MIN), |acc, &day| (acc.0.min(day), acc.1.max(day)));

        let count = |day| {
            let mut bouquet_count = 0;
            let mut adj_count = 0;

            for i in 0..(bloom_day.len()) {
                if bloom_day[i] <= day {
                    adj_count += 1;
                } else {
                    adj_count = 0;
                }

                if adj_count == k {
                    bouquet_count += 1;
                    adj_count = 0;
                }
            }

            bouquet_count
        };

        let left = (min_day..(max_day + 1)).binary_search_min_by(|day| count(day).cmp(&m));

        if left <= max_day {
            left
        } else {
            -1
        }
    }
}

class Solution {
    public long repairCars(int[] ranks, int cars) {  
        long left = 1;
        long right = 0;
        for(int rank:ranks){
            right = Math.max(right,(long) rank * cars * cars);
        }
        while(left<right){
            long mid = left +(right-left)/2;
            if(condition(ranks, cars,mid)){
                right =mid;
            }
            else{
                left = mid+1;
            }
        }
        return left;
    }
    private boolean condition(int [] ranks, int cars, long time){
        for(int rank:ranks){
            cars-=(int)Math.sqrt((double)time/rank);
            if(cars<=0) return true;
        }
        return false;
    }
}

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        def check(t):
            return sum(int((t//r)**0.5) for r in ranks) >= cars
        l, r = 0, min(ranks)*cars*cars
        while l + 1 < r:
            pivot = l + (r - l + 1)//2
            if check(pivot):
                r = pivot
            else:
                l = pivot
        return r

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay):
            return -1
        def check(p):
            ret, count = 0, 0
            for x in bloomDay:
                count = count + 1 if x <= p else 0
                if count == k:
                    count = 0
                    ret += 1
            return ret >= m
        
        l, r = 0, max(bloomDay)
        while l + 1 < r:
            pivot = l + (r - l + 1)//2
            if check(pivot):
                r = pivot
            else:
                l = pivot
        return r