Leetcode: Minimum Number of Days to Make m Bouquets

問題

Given an integer array bloomDay, an integer m and an integer k. We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden. The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet. Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1. ・ bloomDay.length == n ・1 <= n <= 10^5 ・1 <= bloomDay[i] <= 10^9 ・1 <= m <= 10^6 ・1 <= k <= n

整数配列の bloomDay と整数 m , k が与えられる。 m 個のブーケを作成するため、 k 個の隣接した花を摘まなくてはならない。花園は n 個の花があり、 i 番目の花は bloomDay\[i\] 日目に咲き、その時ブーケとして使用することができる。 m 個のブーケを作成するために必要な最小日を求めなさい。もし不可能であれば -1 を返すこと。

考察

ぱっと問題を呼んだ感じ日にちを小さい順に見ていく都度条件を満たすかを確認していくパターンが考えられるが、bloomDay の個数、 bloomDay[i] の値を考えると容易にTimeLimitExceedになってしまうことがわかる。

そこで発想を変えて、ちょうどブーケを作れるタイミングを考えてみる。

ちょうどブーケが作れる日にちを X とすると、この問題は「ブーケをm個ちょうど作れる日にち X を求めよ」という問題に変形ができる。

また現在見ている日にちを a とした時

a < X : ブーケは m 個より少ない
a > X : ブーケは m 個より大きい

ということがわかるため、a の値が X へ徐々に近づける条件が揃っており、このことから二分探索で X を求められることがわかる。

実装

まずは境目となる a の範囲を考えてみる。 a は bloomDay の値の範囲内に必ず収まるため、

min(bloomDay) <= a <= max(bloomDay)

という範囲内にあることがわかる。

よってコードで表すと

int minA = *min_element(bloomDay.begin(), bloomDay.end());
int maxA = *max_element(bloomDay.begin(), bloomDay.end());

と表すことができる。

次に境目を a としたときに、隣接する花を k 個使って、 m 個ブーケが作れるかを考える。

これはコードで表すとこの様になる。

int flowers = 0, bouquets = 0;
for(int i = 0; i < bloomDay.size(); i++) {
  if(bloomDay[i] > a) {
    // この時まだ通過していない日にちとなるため積んだ花の個数をリセットする
    flowers = 0;
  } else {
    flowers += 1;
    if(flowers == k) {
       // 積んだ花の個数がkに達したので、積んだ花をブーケにする
       bouquets += 1;
       flowers = 0;
    }
  }
}

そして境目となる a を見つけるために二分探索を行う。

a = ((minA + maxA) / 2);

a の範囲を絞る処理を書く。


if(bouquets < m) {
  // a は X より小さいので、minAを大きくする
  minA = a + 1;
} else {
  // a は X より大きいので、maxAを小さくする
  maxA = a;
}

2分探索で進めていき、最終的には bloomDay 内に存在する値を取り出したいためブーケの数が m より少ない場合は、minA の値に a + 1 を代入し、そうでない場合 maxA に a を代入する。

後者の場合はブーケの数がちょうど m 個作れている場合も含まれているが、この値を見つけたときにreturnをしてしまうと、a は単純に minA と maxA を2で割ったものであるため、 bloomDay に含まれていない値を返してしまう可能性がある。

よって bloomDay 内に存在する X を求めたいので、これらの処理を

while(minA < minB) {
  .. 上の処理
}

という条件の while文で囲むことで、最終的に minA の値は X になる。

これはブーケの条件を満たす bloomDay に含まれていない a を見つけた時, maxA の値が徐々に減らされていき、最終的にブーケの条件を満たす最小値 ( = X) になるためである。

最小値がなぜ Xになるかというと bloomDay[i] > a という条件を元に花を積んでいるので、m個ブーケを積むことができ且つ最小の値という a は bloomDay に存在することになる。

最終的に下記のコードになる。

public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if(bloomDay.size() < (m * k)) return -1;
        
        int minA = *min_element(bloomDay.begin(), bloomDay.end());
        int maxA = *max_element(bloomDay.begin(), bloomDay.end());
        
        while(minA < maxA) {
            int a = (minA + maxA) / 2;
            int flowers = 0, bonquets = 0;
            for(int i = 0; i < bloomDay.size(); i++) {
                if(bloomDay[i] > a) {
                    flowers = 0;
                } else {
                    flowers += 1;
                    if(flowers == k) {
                        bonquets += 1;
                        flowers = 0;
                    }
                }
            }
            
            if(bonquets < m) {
                minA = a + 1;
            } else {
                maxA = a;
            }
        }
        
        return minA;