Statistics

Problem Statement for "Runway"

Problem Statement

Our mile-long airport runway needs to be inspected. We have made patches on it over the last year. The patches that have been completely covered by later patches so that no area is left exposed don't have to be inspected, but all the other patches do.

Create a class Runway that contains a method inspect that is given int[]s x0 and x1 indicating the locations of the patches and that returns the number of patches that must be inspected.

The ith elements of x0 and x1 refer to the end positions of a single patch. The elements are given in chronological order with earlier patches before later patches. A patch includes its endpoints and all the area between them. A patch whose endpoints are both the same has NO area and never needs to be inspected.

Definition

Class:
Runway
Method:
inspect
Parameters:
int[], int[]
Returns:
int
Method signature:
int inspect(int[] x0, int[] x1)
(be sure your method is public)

Constraints

  • x0 and x1 will have the same number of elements, between 1 and 50 inclusive.
  • Each element of x0 and of x1 will be between 0 and 5280 inclusive.

Examples

  1. {3,4,0,2,100,5280}

    {7,2,6,50,500,0}

    Returns: 1

    That last patch covered the entire runway. The earlier patches do not have to be inspected since they are entirely hidden.

  2. {2,6,2}

    {6,3,3}

    Returns: 2

    The patches between 6 and 3, and between 2 and 3 are visible, and completely cover the earlier patch from 2 to 6.

  3. {1,2,3,4,5,6}

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

    Returns: 0

    These are six separate patches, but none of them have any area so no patches are visible.

  4. {123,354,812,123,122,193}

    {100,355,811,124,121,198}

    Returns: 6

  5. {23,433,712,284,323,396,834,234,123,999,304,523,823,444}

    {433,712,284,323,396,834,234,123,999,304,523,823,444,23}

    Returns: 3

  6. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000}

    Returns: 1

  7. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {5250,5249,5248,5247,5246,5245,5244,5243,5242,5241,5240,5239,5238,5237,5236,5235,5234,5233,5232,5231,5230,5229,5228,5227,5226,5225,5224,5223,5222,5221,5220,5219,5218,5217,5216,5215,5214,5213,5212,5211,5210,5209,5208,5207,5206,5205,5204,5203,5202,5201}

    Returns: 50

  8. {5}

    {3}

    Returns: 1

  9. {5009}

    {5009}

    Returns: 0

  10. {4,7,6,5,4}

    {6,7,6,5,4}

    Returns: 1

  11. {4,7,6,5,4}

    {6,6,5,4,4}

    Returns: 3

  12. {4,7,6,5,4000}

    {6,6,5,4,5}

    Returns: 2

  13. {9,2,55,33,22,7,7,7,7}

    {500,8,52,37,28,8,2,7,3}

    Returns: 7

  14. {3000,3000,3000,3000,3000,3000,3000}

    {8,2,8,15,16,15,12}

    Returns: 3

  15. {99,33,44,66,21,33,92,31,44,83,82}

    {199,133,144,166,121,133,192,131,144,183,182}

    Returns: 7

  16. {0,0}

    {5280,5279}

    Returns: 2

  17. {4643, 5180, 2379, 3970, 408, 5159, 3698, 1397, 5008, 2592, 1712, 932, 3510, 3469, 3757, 4023, 4862, 4984, 1255, 4113, 1157, 3216, 3851, 4506, 1559, 536, 4471, 3924}

    {4825, 3712, 258, 894, 1893, 1960, 3959, 3095, 3403, 986, 3488, 1368, 2732, 4099, 3023, 3952, 5056, 1787, 5179, 4006, 4, 3312, 3034, 3829, 851, 2843, 3105, 3265}

    Returns: 8

  18. {2264, 4623, 1092, 2092, 203, 504, 2172, 2974, 2697, 1197, 5115, 2527, 98, 4475, 4921, 1906, 1495, 2006, 1880, 3587, 2895, 1376, 4095, 1117, 4328, 587, 3564, 3529, 4726, 1449, 3463, 2345, 2394}

    {1210, 2007, 3824, 2921, 1518, 2328, 4776, 1741, 4886, 2438, 81, 1928, 3838, 576, 2600, 318, 4429, 1470, 946, 503, 3690, 4809, 4667, 2908, 2489, 1116, 5141, 5251, 3053, 1243, 1344, 2872, 4382}

    Returns: 12

  19. {3123, 4576, 700, 3586, 3366, 3468, 1791, 2351, 5073, 5041, 930, 1601, 4504, 2191, 163, 332, 2019, 1938, 1880, 3318, 3308, 4029, 2592}

    {5250, 2280, 1876, 1628, 3687, 1264, 4232, 4684, 1068, 1523, 5142, 4046, 3584, 2012, 511, 122, 4187, 1979, 1254, 5002, 358, 1179, 4604}

    Returns: 8

  20. {1331, 4925, 2074, 1316, 3622, 3428, 1856, 4067, 3687, 2031, 1065, 2846, 1023, 2337, 3437, 4437, 2961, 3686, 684, 3839, 4565, 3801, 3089, 2597, 1597, 166, 384, 2878, 1815, 1362, 4435, 3109, 511, 2584, 4716, 242, 1689}

    {1917, 2918, 4077, 4608, 279, 3624, 2293, 2123, 2741, 1017, 1864, 151, 800, 4232, 949, 4272, 4224, 2778, 886, 841, 1311, 602, 2978, 3099, 1125, 3993, 1519, 4939, 4974, 1302, 5245, 3550, 1091, 3406, 4798, 4274, 2334}

    Returns: 7

  21. {3025, 53, 3390, 5277, 4311, 4660, 96, 1354, 3921, 4138, 3291, 1946, 4251, 716, 3514}

    {454, 1168, 177, 112, 1391, 667, 4477, 3409, 3914, 5220, 1501, 442, 4165, 1214, 3085}

    Returns: 10

  22. {184, 1961, 1602, 2434, 2312, 2956, 1954, 1891, 2091, 3512, 3152, 385, 4589}

    {4327, 1443, 5113, 1406, 2700, 2379, 5039, 2384, 3873, 2926, 277, 161, 3785}

    Returns: 7

  23. {2750, 5202, 877, 3092, 1082, 5085, 1735, 1391, 6, 1023, 1425, 4906, 957, 4798, 3441, 3528, 4165, 3620, 3338, 2275, 3981, 1124, 391, 2576, 4980, 1831, 2123, 2008, 1516, 760, 4323, 919, 3923, 1368, 3755, 4934}

    {214, 2874, 3591, 366, 4149, 2468, 798, 4526, 2933, 3204, 3220, 4934, 5078, 1078, 1380, 935, 4849, 558, 650, 239, 3948, 4918, 589, 4882, 4281, 1734, 3891, 530, 1763, 1258, 3156, 4766, 1184, 1411, 2126, 1709}

    Returns: 13

  24. {2564, 4498, 4633, 1808, 3473, 4645, 753, 307, 3409, 952}

    {3247, 3531, 3043, 1146, 3131, 4436, 1412, 728, 347, 841}

    Returns: 6

  25. {2682, 2990, 60, 36, 2551, 83, 4185, 3622, 4946, 4849, 2882, 984, 3393, 4028, 4270, 4684, 5176, 4837, 620, 2477, 1660, 2315, 1527}

    {2590, 281, 505, 4224, 1056, 5148, 3926, 3234, 1041, 2326, 2463, 4462, 346, 172, 1218, 3899, 2143, 2605, 3521, 4923, 2916, 2511, 4201}

    Returns: 7

  26. {4519, 4926, 2968, 4678, 2993, 5216, 2700, 5132, 228, 4110, 3952, 4522, 2940, 3413, 1147, 31, 1064, 4652, 4924, 815}

    {1699, 4587, 411, 1539, 32, 735, 1001, 5138, 1704, 1064, 5173, 4784, 2337, 566, 4419, 4696, 681, 3159, 2975, 2115}

    Returns: 6

  27. {3084, 1447, 610, 4402, 3039, 2092, 544, 80, 3259, 5146, 2309, 4283, 3795, 2246, 3284, 3437, 2840, 711, 455, 4486, 4688, 4112, 4424, 2784, 18, 4561, 992, 4762, 4239, 674, 4541, 4174, 3941, 5241, 1053, 995, 823, 546, 2586, 1087, 4368, 2634, 1012, 1039, 3248, 4515, 3702}

    {2337, 1960, 1188, 3034, 3489, 4926, 3240, 3487, 4902, 3132, 2211, 3827, 2493, 3593, 995, 1831, 3622, 3687, 1229, 431, 4492, 2635, 300, 1611, 786, 1343, 1066, 1601, 2097, 1079, 4467, 2282, 2771, 3402, 4795, 3086, 3112, 2849, 1478, 4103, 5217, 3034, 2299, 2175, 2452, 1746, 5009}

    Returns: 8

  28. {2704, 1859, 3186, 66, 5252, 3859, 1378, 2961, 313, 1140, 1168, 2008, 202, 1145, 3319, 3644, 1845, 1888, 169, 5245, 3560, 4594, 2455, 4883, 4502, 2704, 4498, 1528, 3702, 453, 5160, 901, 4484, 637, 3522, 5128, 3268, 3969, 3846, 912}

    {2763, 526, 3887, 2737, 4650, 4623, 3379, 1041, 2221, 4608, 2341, 4027, 2821, 4445, 5009, 3825, 3487, 1492, 5149, 831, 3382, 5166, 4964, 3603, 787, 1660, 4892, 294, 2036, 3502, 3649, 5054, 1240, 1273, 2385, 4280, 4493, 1003, 1231, 1401}

    Returns: 14

  29. {2718, 5139, 185, 2167, 580, 1412, 2627, 2060, 4288, 1833, 2527, 4295, 718, 3816, 3238, 1995, 274, 487, 4251, 4563, 4871, 2542, 2144, 1151, 466, 1532, 1344, 2378, 211, 4953, 1993, 930, 4077}

    {3544, 2185, 5206, 1054, 842, 4193, 4390, 2057, 4983, 852, 2135, 1590, 3905, 1481, 3394, 1820, 5126, 1174, 1653, 4639, 3281, 1960, 4255, 202, 1098, 1780, 50, 923, 513, 1, 1998, 5020, 1655}

    Returns: 5

  30. {3961, 4982, 4064, 4961, 2654, 861, 4261, 2818, 1144, 4817, 4729, 4637, 218, 3408, 754, 3128}

    {987, 4387, 2838, 3226, 4449, 5155, 1915, 1622, 623, 2209, 2913, 112, 441, 3991, 4139, 1694}

    Returns: 7

  31. {3290, 2758, 2664, 826, 4453, 1912, 308, 3290, 90, 4945, 3178, 2149, 1694, 3708, 1255, 3595, 5115, 1376, 1077, 1669}

    {2567, 2010, 2971, 1643, 4184, 4728, 4713, 3359, 4107, 648, 5094, 4269, 463, 5064, 3794, 2682, 1555, 2362, 4479, 2313}

    Returns: 5

  32. {4241, 4229, 4228, 4228, 4234, 4232, 4230, 4242, 4232, 4231, 4242, 4235, 4236, 4241, 4241, 4233, 4234, 4235, 4234, 4232, 4241, 4236, 4231, 4232, 4234, 4242, 4234, 4237, 4234, 4233, 4235, 4228, 4234, 4241, 4233, 4238, 4228, 4231, 4237, 4237, 4230, 4229, 4231}

    {4242, 4229, 4232, 4229, 4237, 4231, 4228, 4228, 4236, 4230, 4232, 4232, 4232, 4229, 4235, 4228, 4242, 4241, 4239, 4232, 4238, 4237, 4242, 4230, 4229, 4240, 4242, 4234, 4235, 4234, 4229, 4239, 4236, 4228, 4235, 4229, 4233, 4242, 4239, 4229, 4232, 4238, 4236}

    Returns: 5

  33. {4792, 4789, 4791, 4791, 4790, 4792, 4790, 4790, 4790, 4792, 4789, 4790, 4792, 4789, 4792, 4792, 4791, 4792, 4791, 4791, 4791, 4790, 4792, 4791, 4791, 4789, 4791, 4792, 4792, 4791, 4789, 4790, 4792}

    {4789, 4789, 4790, 4790, 4790, 4791, 4792, 4790, 4792, 4790, 4790, 4791, 4790, 4791, 4789, 4792, 4790, 4792, 4791, 4792, 4789, 4789, 4789, 4789, 4789, 4790, 4790, 4790, 4790, 4792, 4791, 4791, 4789}

    Returns: 1

  34. {3886, 3892, 3889, 3885, 3890, 3891, 3892, 3885, 3890, 3886, 3891, 3887, 3887, 3889, 3892, 3886, 3883, 3886, 3883, 3887, 3887, 3885, 3891, 3889, 3891, 3892, 3885, 3891, 3892, 3891, 3886, 3888, 3889, 3885, 3889, 3885, 3883, 3889, 3889, 3892}

    {3890, 3887, 3889, 3891, 3889, 3892, 3884, 3892, 3883, 3892, 3889, 3888, 3884, 3886, 3891, 3889, 3883, 3885, 3888, 3885, 3883, 3891, 3887, 3889, 3885, 3889, 3892, 3891, 3884, 3885, 3889, 3889, 3885, 3891, 3887, 3892, 3883, 3883, 3889, 3890}

    Returns: 3

  35. {1193, 1186, 1184, 1186, 1193, 1196, 1181, 1193, 1195, 1186, 1192, 1188, 1188, 1193, 1189, 1194, 1185, 1190, 1196, 1183, 1195, 1194, 1188, 1193, 1181, 1193, 1184, 1192, 1195, 1190, 1197, 1196, 1197, 1197, 1188, 1182, 1189, 1190, 1191, 1182, 1195}

    {1185, 1193, 1184, 1187, 1192, 1184, 1185, 1197, 1196, 1190, 1183, 1197, 1197, 1185, 1189, 1195, 1191, 1189, 1184, 1196, 1192, 1189, 1187, 1184, 1182, 1192, 1187, 1196, 1191, 1182, 1182, 1192, 1187, 1196, 1182, 1187, 1189, 1187, 1188, 1188, 1181}

    Returns: 3

  36. {15, 9, 21, 20, 7, 11, 5, 6, 11, 15, 21, 14, 20, 12, 18, 21, 7, 12, 16, 13, 10, 8, 12, 14, 12, 20, 18, 7, 9, 13, 10, 15}

    {12, 12, 7, 19, 21, 20, 10, 15, 9, 21, 20, 21, 17, 14, 11, 8, 6, 21, 16, 21, 20, 9, 7, 7, 14, 21, 13, 17, 15, 20, 7, 11}

    Returns: 7

  37. {2363, 2362, 2363, 2363, 2362, 2363, 2363, 2363, 2363, 2362, 2362, 2363, 2362, 2363, 2362, 2363, 2362, 2362, 2362, 2362, 2363, 2363, 2362, 2363, 2362, 2363, 2362, 2363, 2362, 2362, 2362, 2362, 2362, 2362, 2363, 2362, 2362, 2362, 2363, 2362}

    {2363, 2362, 2362, 2363, 2363, 2363, 2362, 2363, 2363, 2363, 2363, 2362, 2363, 2363, 2363, 2363, 2362, 2362, 2362, 2363, 2363, 2363, 2363, 2362, 2363, 2363, 2363, 2363, 2363, 2362, 2363, 2363, 2363, 2362, 2362, 2363, 2362, 2362, 2362, 2362}

    Returns: 1

  38. {2589, 2589, 2593, 2586, 2590, 2583, 2592, 2583, 2593, 2582, 2585, 2583, 2584, 2583, 2583, 2593, 2597, 2594, 2589, 2582, 2592, 2594, 2591, 2589, 2584, 2596, 2595, 2591, 2590, 2590, 2585}

    {2595, 2591, 2594, 2586, 2589, 2592, 2594, 2589, 2595, 2590, 2582, 2592, 2593, 2582, 2589, 2596, 2589, 2595, 2592, 2585, 2589, 2583, 2589, 2589, 2583, 2588, 2594, 2591, 2585, 2586, 2584}

    Returns: 8

  39. {66, 68, 64, 61, 62, 61, 68, 65, 68, 65, 68, 66, 61, 62, 64, 64, 62, 67, 63, 62, 68, 65, 66, 64, 66, 66, 65, 65, 65, 64, 61, 68, 64, 65, 61, 65, 68}

    {65, 61, 66, 65, 64, 68, 62, 66, 62, 68, 62, 61, 61, 64, 63, 66, 62, 65, 63, 62, 62, 65, 67, 67, 66, 68, 64, 66, 64, 67, 65, 68, 64, 67, 65, 61, 68}

    Returns: 3

  40. {1186, 1173, 1176, 1173, 1173, 1173, 1171, 1180, 1175, 1170, 1177, 1184, 1186, 1182, 1186, 1186, 1186, 1180, 1184, 1183, 1177, 1177, 1183, 1171, 1186, 1175, 1178, 1185, 1177, 1183, 1170, 1175, 1172}

    {1170, 1170, 1183, 1168, 1178, 1180, 1171, 1177, 1183, 1179, 1170, 1178, 1170, 1168, 1170, 1168, 1185, 1168, 1186, 1185, 1185, 1168, 1171, 1186, 1177, 1172, 1172, 1185, 1174, 1186, 1181, 1182, 1178}

    Returns: 6

  41. {3911, 3909, 3908, 3911, 3912, 3910, 3910, 3915, 3915, 3914, 3908, 3910, 3913, 3908, 3915, 3908, 3915, 3910, 3915, 3913, 3914, 3911, 3910, 3910, 3911, 3913, 3911, 3915, 3909, 3914, 3910, 3912, 3915, 3913, 3913, 3913, 3910, 3908, 3908, 3913, 3911, 3912, 3908, 3909, 3913, 3912, 3912, 3908}

    {3909, 3913, 3913, 3910, 3913, 3910, 3908, 3915, 3910, 3911, 3910, 3909, 3913, 3911, 3912, 3913, 3909, 3910, 3914, 3914, 3911, 3908, 3908, 3910, 3914, 3912, 3915, 3909, 3908, 3912, 3913, 3911, 3913, 3913, 3913, 3910, 3910, 3914, 3913, 3908, 3912, 3908, 3912, 3909, 3910, 3908, 3914, 3912}

    Returns: 3

  42. {554, 562, 562, 555, 552, 557, 563, 558, 555, 556, 560, 559, 561, 553, 555, 554, 553, 553, 559, 556, 557, 561, 559, 554, 559, 563, 556, 557, 562, 556, 558, 559, 554}

    {559, 558, 561, 555, 562, 561, 557, 558, 560, 555, 561, 560, 563, 556, 557, 563, 562, 559, 554, 555, 553, 562, 559, 557, 555, 557, 561, 554, 557, 562, 561, 557, 558}

    Returns: 7

  43. {550, 550, 549, 542, 548, 544, 550, 551, 543, 551, 547, 548, 552, 547, 551, 551, 543, 544, 542, 544, 547, 545, 550, 550, 552, 552, 543, 552, 542, 542, 552, 546, 542, 550, 552, 551, 547, 548, 549, 545, 552, 550, 550, 542, 549, 544, 545, 551, 548, 543}

    {543, 544, 552, 550, 544, 549, 548, 545, 544, 545, 552, 550, 543, 544, 549, 545, 551, 542, 543, 544, 550, 544, 544, 543, 546, 550, 549, 545, 552, 542, 543, 544, 551, 542, 543, 546, 552, 548, 543, 542, 548, 544, 545, 552, 543, 544, 548, 548, 548, 550}

    Returns: 3

  44. {4700, 4709, 4706, 4695, 4698, 4704, 4700, 4694, 4700, 4708, 4703, 4692, 4703, 4699, 4708, 4698, 4704, 4698, 4703, 4708, 4705, 4703, 4692, 4704, 4697, 4702, 4699, 4705, 4702, 4709, 4703, 4709, 4705, 4704, 4708, 4707, 4700, 4702, 4706, 4698, 4695, 4697}

    {4696, 4699, 4706, 4708, 4693, 4699, 4707, 4708, 4699, 4701, 4705, 4700, 4696, 4707, 4701, 4702, 4700, 4707, 4693, 4699, 4698, 4695, 4693, 4696, 4693, 4703, 4700, 4693, 4695, 4695, 4694, 4706, 4697, 4692, 4694, 4695, 4703, 4704, 4699, 4692, 4693, 4709}

    Returns: 3

  45. {4909, 4911, 4908, 4911, 4908, 4909, 4913, 4908, 4913, 4914, 4912, 4909, 4912, 4913, 4914, 4911, 4913, 4911, 4908, 4915, 4910, 4910, 4915, 4910, 4915, 4912, 4907, 4907, 4912, 4915, 4911, 4907, 4912, 4910, 4913}

    {4911, 4908, 4911, 4909, 4915, 4909, 4913, 4908, 4912, 4913, 4907, 4913, 4908, 4908, 4909, 4909, 4914, 4910, 4909, 4911, 4909, 4910, 4911, 4910, 4912, 4910, 4913, 4915, 4910, 4911, 4909, 4907, 4908, 4911, 4909}

    Returns: 4

  46. {2708, 2709, 2708, 2712, 2709, 2711, 2710, 2712, 2709, 2712, 2710, 2712, 2711, 2711, 2710, 2710, 2710, 2709, 2710, 2712, 2708, 2708, 2708, 2712, 2708, 2710, 2708, 2710, 2709, 2708, 2710, 2712, 2709, 2710, 2709, 2709, 2711, 2710, 2712, 2711, 2711, 2712, 2709, 2708, 2710, 2711}

    {2708, 2712, 2711, 2709, 2710, 2712, 2710, 2708, 2709, 2711, 2708, 2711, 2711, 2711, 2712, 2710, 2709, 2708, 2710, 2708, 2712, 2712, 2711, 2708, 2711, 2709, 2711, 2709, 2711, 2710, 2711, 2712, 2709, 2708, 2709, 2711, 2712, 2708, 2709, 2709, 2710, 2712, 2711, 2710, 2711, 2712}

    Returns: 3

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: