Interview question

Revision en3, by bablu_45, 2019-07-15 20:10:28

Given an array of roses. roses[i] means rose i will bloom on day roses[i]. Also given an int k, which is the minimum number of adjacent bloom roses required for a bouquet, and an int n, which is the number of bouquets we need. Return the earliest day that we can get n bouquets of roses.

Example: Input: roses = [1, 2, 4, 9, 3, 4, 1], k = 2, n = 2

Output: 4

Explanation:

day 1: [b, n, n, n, n, n, b]. The first and the last rose bloom.

day 2: [b, b, n, n, n, n, b]. The second rose blooms. Here the first two bloom roses make a bouquet.

day 3: [b, b, n, n, b, n, b]

day 4: [b, b, b, n, b, b, b]

Here the last three bloom roses make a bouquet, meeting the required n = 2 bouquets of bloom roses. So return day 4.

I am looking for a efficient D.P solution (if possible).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English bablu_45 2019-07-15 20:10:28 60
en2 English bablu_45 2019-07-15 19:12:26 10
en1 English bablu_45 2019-07-15 19:11:47 758 Initial revision (published)