Statistics

Problem Statement for "VacationTime"

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

  1. 3

    3

    {2}

    Returns: 1

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

  2. 4

    3

    {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.

  3. 5

    3

    {4, 1}

    Returns: 1

    Any 3 consecutive days have exactly one meeting within them.

  4. 9

    2

    {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.

  5. 4

    4

    {1, 3}

    Returns: 2

  6. 2

    2

    {1}

    Returns: 1

  7. 5

    1

    {3}

    Returns: 0

  8. 2

    2

    {1}

    Returns: 1

  9. 5

    3

    {4}

    Returns: 0

  10. 3

    1

    {1, 2}

    Returns: 0

  11. 911

    526

    {185, 565, 512, 425, 274, 367, 658, 722, 645, 684, 859, 888, 823, 380, 523, 352, 95, 376, 72, 302, 457, 92, 317, 637, 431}

    Returns: 14

  12. 551

    293

    {108, 82, 51, 322, 16, 532, 180, 140, 363, 435, 478, 504, 484, 294, 274, 224, 7, 262, 193, 411, 513, 169}

    Returns: 9

  13. 143

    4

    {114, 40, 20, 96, 14}

    Returns: 0

  14. 570

    276

    {374, 106, 9, 89, 125, 231, 368, 219}

    Returns: 2

  15. 369

    121

    {265, 260, 131, 173, 95, 108, 152, 117, 248, 227, 13, 256, 186}

    Returns: 3

  16. 987

    160

    {479, 628, 522, 168, 436, 162, 350, 181, 493, 311, 619, 783, 913, 583, 325, 983, 242, 314, 127, 870, 435, 19, 612, 534, 239, 155, 969, 79, 949, 191, 356, 484, 199, 238, 702, 556, 908, 214, 222, 917, 582, 506, 854, 858, 302, 679}

    Returns: 2

  17. 601

    169

    {458, 393, 371, 295, 74, 461, 472, 292, 220, 109, 48}

    Returns: 1

  18. 199

    65

    {6, 87, 117, 65, 115, 44, 149, 11, 143, 29}

    Returns: 2

  19. 560

    510

    {117, 266, 8, 272, 89, 337, 80, 262, 305, 63, 511, 205, 533, 306, 87}

    Returns: 13

  20. 318

    148

    {196, 180, 139, 253, 172, 276, 79, 293, 84, 47, 306, 179, 175, 32, 18, 267, 52, 76}

    Returns: 6

  21. 558

    409

    {23, 390, 95, 25, 21, 327, 43, 36, 312, 442, 485, 80, 333, 181, 435, 225, 291, 360, 428}

    Returns: 12

  22. 248

    81

    {10, 104, 14, 39, 118, 16, 178, 8, 206, 150, 126}

    Returns: 1

  23. 315

    66

    {233, 81, 105, 5, 288, 182, 108, 123, 23, 287, 194, 246, 111, 88, 272}

    Returns: 1

  24. 105

    6

    {14, 59, 10, 98, 42, 4, 28, 1, 89, 61, 37, 3, 17, 82, 58}

    Returns: 0

  25. 368

    344

    {145, 213, 296, 18, 363, 167, 16, 202, 34, 100, 239, 175, 171, 261, 221, 219}

    Returns: 13

  26. 720

    622

    {582, 716, 75, 421, 687, 294, 555, 13, 113, 370, 402, 127, 312, 128, 429, 136, 11, 274}

    Returns: 14

  27. 619

    318

    {152, 578, 158, 317, 111, 84, 174, 497, 556, 286, 10, 559, 293, 541, 466, 552, 561, 229, 362, 549, 190, 442, 207}

    Returns: 8

  28. 607

    551

    {18, 215}

    Returns: 1

  29. 645

    414

    {237, 614, 10, 438, 42, 314, 506, 473, 315, 4, 597, 89, 234, 526, 517, 428, 206, 532, 385, 81, 424, 197, 174, 367, 611, 510, 214, 395, 512}

    Returns: 15

  30. 813

    339

    {396, 546, 312, 343, 139, 376, 583, 472, 238, 751, 393, 723, 14, 361, 793, 144, 683, 564, 627, 9, 500, 607, 105, 154, 750, 533}

    Returns: 7

  31. 661

    442

    {368, 370, 573, 11, 25, 290, 149}

    Returns: 4

  32. 242

    190

    {214}

    Returns: 0

  33. 609

    450

    {174, 525, 75, 93, 608, 12, 261, 61, 102, 340, 597, 106, 207, 222, 243, 391, 141, 77, 56, 328, 566, 400, 218, 468, 214, 487, 551, 310, 536, 535, 320, 151, 54, 371, 572, 266, 107, 410, 533, 364}

    Returns: 26

  34. 582

    509

    {104, 517, 543, 162, 473, 243, 318, 547, 467, 314}

    Returns: 7

  35. 383

    76

    {27, 135, 309, 344, 238, 67, 261, 148, 242, 356, 275, 100, 127, 306, 161, 382, 6}

    Returns: 0

  36. 77

    19

    {39, 43, 64, 6, 72, 68, 3}

    Returns: 0

  37. 437

    189

    {247, 268, 106, 98, 215, 340, 230, 146, 102, 65, 127, 387, 360, 112, 66}

    Returns: 4

  38. 285

    153

    {247, 210, 164, 113, 50, 97, 15, 144, 138, 216, 95, 184, 4, 194, 253, 23, 48, 62, 192}

    Returns: 9

  39. 448

    40

    {124, 115, 207, 327, 215}

    Returns: 0

  40. 735

    400

    {491, 390, 663, 555, 432, 480, 243, 470, 245, 418, 621, 78, 543, 201, 118, 402, 598, 496, 438, 716, 460, 685, 360, 26, 384, 337, 643, 713, 261, 57, 292, 97, 2, 188, 667, 361, 55, 723, 441, 155, 525, 520, 700}

    Returns: 19

  41. 968

    451

    {264, 35, 396, 553, 296, 858, 870, 207, 797, 475, 373, 10, 411, 70, 180, 786, 133, 323, 531, 269, 776, 600, 830, 534, 81, 450, 132, 554, 123, 867, 221, 74, 179, 911, 771, 634, 488, 372, 585, 605, 300, 783, 596}

    Returns: 17

  42. 970

    848

    {179, 538, 364}

    Returns: 3

  43. 628

    442

    {440, 408, 479, 18, 569, 376, 583, 313, 208, 69, 72, 163, 135, 286, 192, 406}

    Returns: 11

  44. 391

    44

    {339, 278, 180, 100, 203, 18, 85, 11, 282, 28, 213, 301, 247, 273, 101, 173, 86}

    Returns: 0

  45. 752

    707

    {13, 7, 271, 304, 591, 742, 241, 308, 670, 84, 273, 550, 293, 609}

    Returns: 11

  46. 441

    246

    {173, 260, 7, 203, 383, 397, 313, 380, 323, 55, 377, 128, 163}

    Returns: 5

  47. 813

    763

    {765, 57, 175, 576, 610, 643, 621}

    Returns: 6

  48. 647

    259

    {452, 439, 198, 36, 123, 644, 109, 167, 494, 441, 253, 193, 332, 272, 116, 271, 87, 86}

    Returns: 4

  49. 916

    193

    {403, 556, 277, 100, 455, 905, 783, 67, 531, 861, 318, 54, 631, 130, 422, 241, 562, 846, 602, 463, 654, 179, 11, 358, 694, 233, 387, 150}

    Returns: 3

  50. 934

    459

    {667}

    Returns: 0

  51. 480

    158

    {33}

    Returns: 0

  52. 960

    63

    {277, 640, 666, 837, 919, 256, 713, 559, 121, 302, 672, 23}

    Returns: 0

  53. 901

    149

    {436, 286, 708, 141, 534, 75, 296, 375, 494, 658, 608, 339, 76, 236}

    Returns: 0

  54. 961

    249

    {861, 834, 813, 407, 915}

    Returns: 0

  55. 816

    557

    {125, 290, 267, 535, 538, 72, 707, 241, 399, 766}

    Returns: 6

  56. 842

    483

    {523, 770, 398, 28, 777, 725, 257, 112, 141, 531}

    Returns: 4

  57. 196

    133

    {187, 164, 120, 61, 153, 137, 67, 15, 75, 96, 4, 145}

    Returns: 7

  58. 714

    705

    {49, 114, 309, 107, 123, 649, 438, 187, 507, 619, 400, 383, 659, 553, 281, 93, 220, 308, 697, 517, 257, 340, 283, 547, 30, 321, 491, 365, 620, 408, 137, 495, 392, 557, 617, 325, 353, 282, 109, 219, 183, 332, 501}

    Returns: 43

  59. 222

    80

    {16, 70, 45, 205, 37, 184, 150, 76, 183, 5, 52, 104, 190, 88, 108, 118, 71, 195, 10, 83, 12, 120, 78, 135, 7, 147, 206, 84, 144, 48}

    Returns: 8

  60. 697

    416

    {275, 369, 447, 362, 479, 341, 47, 582, 403, 188, 608, 10, 430, 211, 439, 472, 332, 655, 366, 325}

    Returns: 11

  61. 360

    8

    {130, 339, 146, 127, 3, 227, 8, 179, 110, 188, 319, 224, 350, 173, 263, 288, 104, 343, 102, 9, 289, 118, 199, 222, 80, 49, 81, 308}

    Returns: 0

  62. 734

    349

    {550, 465, 8, 109, 595, 426, 343}

    Returns: 2

  63. 31

    3

    {7, 11, 29}

    Returns: 0

  64. 917

    878

    {71, 458, 432, 754, 234, 687, 746, 631, 810, 248, 81, 753, 847, 240}

    Returns: 14

  65. 938

    216

    {387, 390, 841, 147, 372, 812, 310, 809, 355, 307, 819, 761, 848, 622, 671, 505, 920, 132, 230, 391, 597, 226, 278, 820, 104, 595, 261, 514, 650, 476, 486, 917, 892, 267, 14, 492, 638, 795, 248, 96, 865, 83, 326, 610, 423}

    Returns: 6

  66. 425

    237

    {137, 238, 23, 180, 412, 195, 39, 264, 203, 316, 12}

    Returns: 6

  67. 259

    153

    {109, 127, 207, 122, 90, 26, 79}

    Returns: 4

  68. 530

    33

    {447, 144, 260, 108, 352, 102, 350}

    Returns: 0

  69. 758

    550

    {329, 526, 638, 496}

    Returns: 3

  70. 599

    409

    {334, 336, 409}

    Returns: 3

  71. 468

    293

    {236, 185}

    Returns: 2

  72. 655

    109

    {51, 42, 31, 479, 268, 234, 420, 164, 203, 290, 602, 39, 302, 281, 293, 310, 269, 257}

    Returns: 0

  73. 894

    277

    {132, 311, 476, 888, 131, 646}

    Returns: 1

  74. 511

    22

    {139, 231, 199, 70, 270, 482, 18, 307, 256, 328, 202, 428, 303, 296, 90}

    Returns: 0

  75. 839

    705

    {687, 346, 380}

    Returns: 3

  76. 1000

    436

    {627, 392, 669, 468}

    Returns: 1

  77. 1000

    654

    {130, 544, 63, 532, 188, 616, 843, 400, 423, 186, 591, 692, 771, 650}

    Returns: 9

  78. 1000

    409

    {446, 558, 772, 796, 649, 249, 283, 233, 473, 982, 80, 799, 26, 943, 298, 296, 706, 605}

    Returns: 6

  79. 1000

    513

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

    Returns: 2

  80. 1000

    315

    {116, 635, 618, 441, 974, 883, 76, 168, 238, 359, 542, 344, 262, 716, 754, 133, 816, 4, 564, 157, 612, 54, 977, 47, 658, 178, 91, 142, 879}

    Returns: 5

  81. 10

    6

    {2, 9}

    Returns: 0

  82. 1000

    361

    {275, 551, 136, 93, 357, 685, 906, 715, 108, 991, 234, 708, 125, 62, 468, 718, 391, 409, 649, 580, 157, 174, 56, 300, 588, 758, 354, 542, 728, 533, 353, 829, 226, 430, 988, 217, 419, 489, 786, 396, 69, 250, 412, 471, 716, 949, 662, 22, 560, 548}

    Returns: 13

  83. 1000

    853

    {194, 97, 613, 719, 133, 555, 918, 308, 550, 535, 516, 975, 349, 337, 35, 234, 163, 40, 122, 762, 148, 181, 605, 633, 954, 562, 870, 696, 524, 744, 212, 319, 645, 476, 266, 202, 657, 720, 671, 289, 128, 765, 530, 915, 463, 849, 13, 656, 499, 635}

    Returns: 43

  84. 1000

    932

    {392, 959, 384, 233, 122, 71, 137, 547, 926, 251, 200, 361, 598, 762, 321, 919, 938, 455, 914, 205, 285, 813, 399, 254, 479, 974, 418, 312, 961, 40, 688, 983, 943, 226, 649, 773, 601, 324, 766, 356, 114, 788, 912, 836, 739, 993, 808, 850, 913, 267}

    Returns: 43

  85. 1000

    356

    {261, 11, 397, 895, 975, 774, 378, 197, 687, 271, 500, 351, 559, 571, 521, 910, 482, 361, 734, 530, 515, 909, 174, 691, 534, 962, 603, 494, 765, 998, 633, 503, 154, 135, 879, 552, 186, 708, 290, 700, 472, 341, 717, 939, 630, 938, 219, 214, 735, 810}

    Returns: 13

  86. 1000

    513

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

    Returns: 2

  87. 3

    3

    {1, 2, 3 }

    Returns: 3

  88. 945

    450

    {2, 53, 88, 45, 3, 6, 89, 452, 753 }

    Returns: 1

  89. 9

    2

    {7, 4, 5, 6, 2 }

    Returns: 0

  90. 1000

    1000

    {1, 3, 5, 7, 9, 78 }

    Returns: 6

  91. 1

    1

    {1 }

    Returns: 1

  92. 3

    3

    {2 }

    Returns: 1

  93. 4

    2

    {2, 1 }

    Returns: 0

  94. 3

    3

    {3 }

    Returns: 1

  95. 10

    5

    {1, 2, 3, 4, 5 }

    Returns: 0

  96. 200

    200

    {1, 198 }

    Returns: 2

  97. 2

    1

    {2 }

    Returns: 0

  98. 10

    5

    {10 }

    Returns: 0

  99. 3

    1

    {3, 1, 2 }

    Returns: 1

  100. 3

    1

    {2, 3, 1 }

    Returns: 1

  101. 3

    1

    {1, 3 }

    Returns: 0

  102. 4

    2

    {3, 4 }

    Returns: 0

  103. 5

    1

    {5 }

    Returns: 0

  104. 2

    2

    {1, 2 }

    Returns: 2

  105. 3

    2

    {2 }

    Returns: 1

  106. 5

    1

    {1, 2, 3, 4, 5 }

    Returns: 1

  107. 5

    3

    {1, 2, 4 }

    Returns: 1

  108. 6

    5

    {6 }

    Returns: 0

  109. 4

    3

    {4 }

    Returns: 0

  110. 5

    3

    {1, 3, 5 }

    Returns: 1

  111. 10

    4

    {1, 2, 3, 4, 5, 10 }

    Returns: 0

  112. 2

    2

    {2 }

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: