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

function minDays(bloomDay: number[], m: number, k: number): number {
    const feasible = (days: number) => {
        let bon = 0, flow = 0;
        for (const bloom of bloomDay) {
            if (bloom > days) {
                flow = 0
            } else {
                bon+= ~~((flow + 1) / k);
                flow = (flow + 1) % k
            }
        }
        return bon >= m
    }

    let left = 0, right = 0;
    for (const bloom of bloomDay) {
        if (bloom > right) {
            right = bloom;
        }
    }
    if (m * k > bloomDay.length) {
        return -1;
    }

    while (left < right) {
        const mid = left + ~~((right - left) / 2);
        if (feasible(mid)) {
            right = mid
        } else {
            left = mid + 1;
        }
    }
    return left
};

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        left, right = min(bloomDay), max(bloomDay)
        def valid(day):
            count, bouquet = 0, 0
            n = len(bloomDay)
            for i, d in enumerate(bloomDay):
                if d > day:
                    bouquet += count // k
                    count = 0
                else:
                    count += 1
            bouquet += count // k
            return bouquet >= m

        while left < right:
            mid = left + (right - left) // 2
            if valid(mid) == False:
                left = mid + 1
            else:
                right = mid
        if valid(right):
            return right
        return -1

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        if ((long) bloomDay.length < (long) m * k) return -1;

        for (int d: bloomDay) {
            max = Math.max(max, d);
            min = Math.min(min, d);
        }

        while (max > min) {
            int mid = (max + min) / 2;

            int curBouqs = countBouquets(bloomDay, mid, k);

            if (curBouqs >= m) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        return min;
    }

    private int countBouquets(int[] bloomDay, int curDay, int k) {
        int flowers = 0;
        int ans = 0;

        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= curDay) {
                flowers++;
                if (flowers == k) {
                    ans++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }
        return ans;
    }
}

object Solution {
  def minDays(bloomDay: Array[Int], m: Int, k: Int): Int = {
    if (bloomDay.length < BigInt(m) * BigInt(k)) return -1

    val min = bloomDay.min
    val max = bloomDay.max

    def countBouquets(bloomDay: Array[Int], curDay: Int, k: Int): Int = {
      bloomDay.foldLeft((0, 0)) {
        case ((flowers, bouquets), day) =>
          if (day <= curDay) {
            if (flowers + 1 == k) (0, bouquets + 1)
            else (flowers + 1, bouquets)
          } else {
            (0, bouquets)
          }
      }._2
    }

    def binarySearch(min: Int, max: Int): Int = {
      if (min >= max) min
      else {
        val mid = (min + max) / 2
        val curBouqs = countBouquets(bloomDay, mid, k)
        if (curBouqs >= m) binarySearch(min, mid)
        else binarySearch(mid + 1, max)
      }
    }

    binarySearch(min, max)
  }
}

class Solution:
    def minDays(self, b: List[int], m: int, k: int) -> int:
        if m * k > len(b):
            return -1
       
        def has_enough_bouquets(day):
            c = 0
            res = 0
            for i in b:
                if day >= i:
                    c += 1
                else:
                    c = 0
                if c == k:
                    res += 1
                    c = 0
            return res >= m
        l = inf
        r = -inf
        for i in b:
            l = min(l,i)
            r = max(r,i)
        ans = 0
        while l <= r:
            mid = l + (r -l) // 2
            if has_enough_bouquets(mid):
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans

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)
        pivot = l + (r - l + 1)//2
        while l + 1 < r:
            if check(pivot):
                r = pivot
            else:
                l = pivot
            pivot = l + (r - l + 1)//2
        return r

class Solution {
public:
    int minDays(vector<int> const& bloomDay, int m, int k) {
        int n = bloomDay.size();
        if (n < (long)m * k) return -1;
        function<bool(int)> solve = [&](int t) -> bool {
            int cnt = 0, c = 0;
            for (int i = 0; i < n; ++i) {
                if (bloomDay[i] <= t) {
                    c++;
                    if (c >= k) cnt++, c = 0;
                }else c = 0;
            }
            return cnt >= m;
        };
        int lo = 1, hi = *max_element(begin(bloomDay), end(bloomDay));
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            if (solve(mi)) hi = mi;
            else lo = mi + 1;
        }
        return lo;
    }
};