TopCoder problem "VacationTime" used in SRM 477 (Division II Level One)

Problem Statement

The king and the queen want to go on a vacation together. Since the queen seldom asks for anything, the king is more than willing to reschedule his meetings if they conflict with the vacation.

The vacation must last for K contiguous days, and must lie between day 1 and day N inclusive. You are given int[] workingDays, where each element is a day on which the king has a meeting scheduled. The king will have at most one meeting scheduled per day. Return the minimum number of meetings that must be rescheduled so that the king and the queen can have a happy vacation.

Definition

Class:	VacationTime
Method:	bestSchedule
Parameters:	int, int, int[]
Returns:	int
Method signature:	int bestSchedule(int N, int K, int[] workingDays)
(be sure your method is public)

Constraints

N will be between 1 and 1000, inclusive.

K will be between 1 and N, inclusive.

workingDays will contain between 1 and 50 elements, inclusive.

Each element of workingDays will be between 1 and N, inclusive.

Elements of workingDays will be distinct.

Examples

{2}

Returns: 1

The vacation must last from day 1 to day 3. Hence, the meeting on day 2 must be rescheduled.

{3, 1, 2}

Returns: 2

There are two options for the vacation: days 1 to 3, or days 2 to 4. The first option would require 3 meetings to be rescheduled, and the second requires 2 meetings to be rescheduled.

{4, 1}

Returns: 1

Any 3 consecutive days have exactly one meeting within them.

{7, 4, 5, 6, 2}

Returns: 0

The king will not have to reschedule any meetings, but the queen will have to wait until day 8 for the vacation to start.

{808, 459, 792, 863, 715, 70, 336, 731}

Returns: 2

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10884

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14157&pm=10884

Writer:

keshav_57

Testers:

PabloGilberto , ivan_metelsky , mohamedafattah

Problem categories:

Simple Search, Iteration