Statistics

Problem Statement for "SmartElevator"

Problem Statement

You have been put in charge of writing the sofware that powers an elevator in a very tall office building. Because there is only one elevator in the building, and many floors, the designers of the elevator gave it the capacity to remember past usage history. By assuming that the employees will probably use the elevator in the same ways and at the same times each day (arriving at work, going to the cafeteria, leaving for the day), the software can be a much better judge of where to travel and when. For example, if it's currently on the fifth floor, and it knows that the next employee to use the elevator will be on the third floor, it can travel there early so that the employee will not have to spend any time waiting.

Given the arrival times, starting floors, and destination floors of each employee for the day, determine the fastest time in which the elevator can get each employee to his or her destination. The elevator starts on floor 1 at time 0. Travelling from floor p to floor q takes (abs(p - q)) units of time. Also, the elevator may stand still for any length of time, if that is optimal. Assume that it takes no time for employees to enter or exit the elevator. Your method should return the minimal value of T such that, at time T, all employees have arrived at their destinations. Employee i corresponds to the ith element of each input parameter.

Definition

Class:
SmartElevator
Method:
timeWaiting
Parameters:
int[], int[], int[]
Returns:
int
Method signature:
int timeWaiting(int[] arrivalTime, int[] startingFloor, int[] destinationFloor)
(be sure your method is public)

Constraints

  • arrivalTime will contain between 1 and 5 elements, inclusive.
  • arrivalTime, startingFloor, and destinationFloor will all contain the same number of elements.
  • Each element in arrivalTime will be between 1 and 1000000, inclusive.
  • Each element in startingFloor will be between 1 and 1000000, inclusive.
  • Each element in destinationFloor will be between 1 and 1000000, inclusive.
  • For all valid i, startingFloor[i] will never be equal to destinationFloor[i].

Examples

  1. {5}

    {30}

    {50}

    Returns: 49

    In this example, there is only one passenger. He will arrive on floor 30 at time 5, but the elevator will not be able to get to floor 30 until time 29. It will then pick up the employee and drop him off at floor 50 at time 49.

  2. {100}

    {30}

    {50}

    Returns: 120

    This is the same as example 0, but now the elevator can be ready at floor 30 when the employee arrives at time 100. It will still take 20 units of time to reach floor 50, dropping off the passenger at time 120.

  3. {10,120}

    {1,100}

    {210,200}

    Returns: 230

    The first employee will be picked up at time 10 on floor 1. At time 109, the elevator will arrive at floor 100. Here, it will wait 11 units of time until the second employee arrives and gets on (at time 120). It will then take another 100 units of time to reach floor 200 to drop off the second employee, and at time 230 it will finally arrive at floor 210 to drop off the first employee.

  4. {10,500}

    {1,100}

    {210,200}

    Returns: 600

    This is the same as example 2, but now the second employee doesn't arrive until time 500. In this case, it makes more sense for the elevator to drop the first employee off immedately, and then return to floor 100 to wait for the second employee.

  5. {1000,1200,1600,2000,2400}

    {500,500,500,500,500}

    {700,300,700,300,700}

    Returns: 2600

    The elevator should wait at floor 500 until time 2000, picking up the first four passengers as they arrive. It should drop off the second and fourth employees on floor 300, then return to floor 500 to pick up the fifth employee, and finally drop off the first, third, and fifth employees on floor 700.

  6. {503868,509600,662448,251624,854952}

    {337034,470546,867834,645090,925407}

    {885895,271701,874608,720490,64409}

    Returns: 1953239

  7. {280588,194163,500203,615750,391972}

    {140458,766726,949141,639618,53743}

    {317993,547173,383765,955719,555977}

    Returns: 1865902

  8. {649993,383798,165693,839646,588106}

    {311908,484055,118606,835692,81221}

    {376794,315990,904736,264080,980736}

    Returns: 2204277

  9. {618252,63079,179886,999752,521772}

    {580544,535366,403881,334607,538945}

    {680185,865721,180603,990544,536660}

    Returns: 1660259

  10. {9745,474209,527076,867645,664252}

    {903910,650294,244553,287290,488226}

    {9925,881085,871089,408052,826621}

    Returns: 2321942

  11. {399923,328162,596453,163285,868557}

    {463136,245611,268724,119067,263689}

    {658075,712563,540012,269193,511632}

    Returns: 1317431

  12. {757355,839558,634456,343241,349073}

    {588309,646597,24909,491712,517048}

    {824698,6540,483511,481147,416068}

    Returns: 2252403

  13. {404948,820298,580803,234161,698332}

    {292622,129160,955035,229400,292686}

    {919936,992665,382525,600151,331248}

    Returns: 2293943

  14. {173672,316489,391757,895815,262559}

    {109428,875479,994112,553905,377356}

    {651117,875529,601223,203208,856713}

    Returns: 1849260

  15. {649667,281856,687356,27425,278637}

    {430606,799987,569474,983034,4498}

    {260895,597101,438465,26077,849192}

    Returns: 2214130

  16. {933662,808333,764215,298169,450424}

    {971527,335039,414405,692034,642594}

    {414995,642486,412148,536256,756609}

    Returns: 1915461

  17. {686229,756395,265028,951720,10771}

    {433637,907582,743565,270263,787994}

    {4010,217396,494540,284416,985452}

    Returns: 1995199

  18. {848545,825654,732235,193061,336177}

    {378962,585171,463231,447399,971837}

    {361248,604183,120275,961159,451487}

    Returns: 1861422

  19. {579805,650092,634768,736714,91556}

    {482198,331775,869088,594113,421290}

    {288469,341489,855859,564515,556784}

    Returns: 1426578

  20. {935236,954985,640955,642511,622686}

    {367450,544485,984788,698835,581282}

    {67912,37810,712439,895936,517591}

    Returns: 1931765

  21. {51311,559594,821138,461772,119411}

    {100645,504328,899360,851020,424070}

    {888598,271274,503561,277291,354857}

    Returns: 1527445

  22. {391387,546634,138301,332921,8980}

    {802850,317642,162023,419643,880150}

    {796478,898825,265844,121424,239581}

    Returns: 1905218

  23. {658272,353350,325056,569201,328083}

    {517463,272110,425519,757645,543346}

    {985375,67041,853411,735867,475529}

    Returns: 1655943

  24. {348667,461500,443331,53929,889252}

    {669166,16918,530780,369810,339866}

    {796470,218529,851359,701402,265893}

    Returns: 1548691

  25. {232388,921255,483277,695101,248346}

    {152943,854341,867762,404024,376113}

    {952420,800923,242708,234296,412166}

    Returns: 1749989

  26. {616878,726831,901741,870324,415578}

    {976113,472225,72398,969217,510984}

    {447322,253595,632625,69957,400083}

    Returns: 2444936

  27. {734499,653925,862064,227113,735658}

    {378211,60659,595387,592417,543914}

    {916544,112996,427341,537069,645708}

    Returns: 1845902

  28. {78770,511362,442964,604443,185192}

    {792866,360086,245861,694107,839419}

    {295413,599847,908045,898631,975972}

    Returns: 1853634

  29. {215380,667555,524095,365633,789191}

    {425748,674924,650414,308479,694268}

    {638073,267798,761209,943103,857746}

    Returns: 1713331

  30. {20964,316933,803639,856181,881368}

    {952388,63352,523484,885883,869581}

    {515369,373889,392828,680418,402925}

    Returns: 1765529

  31. {885593,243163,678984,854150,184447}

    {82909,216155,391576,696021,177092}

    {39145,390830,93395,892921,761379}

    Returns: 1885191

  32. {619859,504425,2319,189556,647448}

    {960695,64919,952654,407855,182602}

    {658966,400945,901915,796838,830154}

    Returns: 1727270

  33. {775397,261225,870141,287698,884334}

    {82225,958610,998971,413596,21922}

    {769962,78706,477861,237168,258488}

    Returns: 2724059

  34. {421449,574649,797752,784920,336692}

    {472305,959024,641923,170345,499085}

    {792675,651106,103930,475843,331171}

    Returns: 2186030

  35. {11675,539539,174536,897118,741756}

    {301058,350067,583531,630213,389612}

    {785568,217617,147014,708908,916002}

    Returns: 1789035

  36. {374847,152557,243998,566155}

    {336998,837829,622573,305177}

    {194612,543368,655451,282975}

    Returns: 1481045

  37. {469472,799661}

    {82768,730529}

    {911315,385273}

    Returns: 1824061

  38. {28919,885249,253930,5027,353757}

    {92859,889331,148080,222125,606689}

    {22203,3510,510507,498462,744321}

    Returns: 1881002

  39. {426051,551496}

    {963083,558989}

    {802134,222209}

    Returns: 1703956

  40. {755400,896007,527299}

    {512881,913948,371655}

    {333906,338968,893683}

    Returns: 1649634

  41. {657406,135491,512248}

    {82036,472474,150324}

    {325997,877677,579011}

    Returns: 1453047

  42. {489482,322087,479484,999437}

    {435335,419577,544568,960976}

    {17414,653898,348218,586072}

    Returns: 1942999

  43. {912745,982608}

    {812441,926500}

    {895748,54030}

    Returns: 1899274

  44. {852584,25602}

    {15275,828491}

    {137978,695948}

    Returns: 1764409

  45. {269982,534100}

    {334413,978591}

    {861993,887338}

    Returns: 1069843

  46. {637816,812483,467944,254882}

    {347994,880466,760808,350479}

    {253288,343166,51193,466878}

    Returns: 1709738

  47. {119927}

    {556235}

    {940980}

    Returns: 940979

  48. {967516,225475,509009}

    {466245,863441,446353}

    {360126,562274,190979}

    Returns: 1535902

  49. {277195,702787}

    {628524,307760}

    {470085,572392}

    Returns: 1181990

  50. {10100,144577,471027,87191}

    {134544,642004,54929,102206}

    {78951,416900,273668,45410}

    Returns: 1283206

  51. {300161,862285,175480}

    {311923,952845,103103}

    {488708,420920,967581}

    Returns: 1586619

  52. {629244,739414,472337,564743}

    {347940,844293,460120,171307}

    {521860,627473,581835,322769}

    Returns: 1454549

  53. {389057,720342,485407,518702,700022}

    {119832,203932,8456,735146,444926}

    {999170,213208,878627,511508,482222}

    Returns: 1962856

  54. {907095,240270,756453,460740,694995}

    {686417,355218,985186,3484,480186}

    {178900,791990,388358,985184,631271}

    Returns: 2248728

  55. {270050,62262,539664,549663,2356}

    {660551,326347,203949,896704,600372}

    {445306,686373,538408,656847,526904}

    Returns: 1683817

  56. { 775397, 261225, 870141, 287698, 884334 }

    { 82225, 958610, 998971, 413596, 21922 }

    { 769962, 78706, 477861, 237168, 258488 }

    Returns: 2724059

  57. { 1, 1, 1, 1, 1 }

    { 1, 1, 1, 1, 1 }

    { 1000, 1000, 1000, 1000, 1000 }

    Returns: 1000

  58. { 1000000, 1000000, 1000000, 1000000, 1000000 }

    { 1, 2, 3, 4, 5 }

    { 2, 3, 4, 5, 6 }

    Returns: 1000005

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: