Delivery Promise Date

easy

A large online store shows every shopper a promise on the product page: "Order now, get it by Thursday." Promise a day too early and the store pays for it in refunds and support tickets; promise too late and the shopper buys elsewhere. You are writing the function that computes that promise.

Days are numbered from 0, and day 0 is a Monday, so day % 7 is 0 for Monday through 6 for Sunday.

A day is a business day when it is a weekday (Monday to Friday) and it is not listed in holidays. The warehouse and the carrier both work on business days only.

An order is handled like this:

Start. If the order is placed on a business day and strictly before the cutoff (orderMinute < cutoffMinute), processing starts that same day. Otherwise it starts on the next business day after orderDay.
Handling. Picking and packing takes handlingDays business days. The parcel ships on the business day that is handlingDays business days after the start day. With handlingDays = 0 it ships on the start day.
Transit. The carrier needs transitDays business days. The parcel is delivered on the business day that is transitDays business days after the ship day.

Return the day number of the promised delivery.

Example

orderDay = 4 (a Friday), orderMinute = 780 (13:00), cutoffMinute = 840 (14:00), handlingDays = 1, transitDays = 1, holidays = [].

The order beats the cutoff, so processing starts on Friday, day 4. One business day of handling skips the weekend: it ships on Monday, day 7. One business day in transit delivers it on Tuesday, day 8. The answer is 8.

Example 1

Input

[
  "0",
  "600",
  "840",
  "0",
  "2",
  "[]"
]

Output

Explanation. Monday before the cutoff: ships Monday, two business days in transit.

Example 2

Input

[
  "0",
  "900",
  "840",
  "0",
  "2",
  "[]"
]

Output

Explanation. After the cutoff, processing starts Tuesday.

Example 3

Input

[
  "4",
  "780",
  "840",
  "1",
  "1",
  "[]"
]

Output

Explanation. Handling on Friday skips the weekend: ships Monday, delivered Tuesday.

Example 4

Input

[
  "5",
  "540",
  "840",
  "0",
  "3",
  "[]"
]

Output

Explanation. A Saturday order starts on Monday, day 7.

Example 5

Input

[
  "0",
  "600",
  "840",
  "1",
  "2",
  "[1,3]"
]

Output

Explanation. Holidays on days 1 and 3 push both handling and transit.

Example 6

Input

[
  "0",
  "840",
  "840",
  "2",
  "1",
  "[]"
]

Output

Explanation. Exactly at the cutoff counts as too late.

Example 7

Input

[
  "2",
  "100",
  "840",
  "0",
  "1",
  "[2]"
]

Output

Explanation. An order placed on a holiday starts on the next business day.

Example 8

Input

[
  "25",
  "1439",
  "1440",
  "3",
  "5",
  "[35]"
]

Output

Explanation. A late Friday order still beats a midnight cutoff; a Monday holiday adds a day.

Example 9

Input

[
  "6",
  "0",
  "1",
  "0",
  "1",
  "[0,6,7,8,9]"
]

Output

Explanation. Sunday order; Monday to Wednesday are holidays, so it starts on Thursday and arrives on Friday.

Follow-up: Peak season gives the carrier a backlog: a promise computed for 50,000 orders a second must not walk the calendar one day at a time. Can you answer each order in time logarithmic in the number of holidays, whatever `handlingDays` and `transitDays` are?

Constraints:

- `0 <= orderDay <= 10^6` - `0 <= orderMinute <= 1439` - `1 <= cutoffMinute <= 1440` - `0 <= handlingDays <= 30` - `1 <= transitDays <= 30` - `0 <= holidays.length <= 10^4` - `holidays` is sorted in strictly increasing order, and every value is between `0` and `2 * 10^6`. A holiday may fall on a weekend, where it changes nothing.

Views: 3