Statistics

Problem Statement for "OneHandScheduling"

Problem Statement

Misof recently had an accident in which he managed to cut his left hand on some broken glass. He is now "all right" - meaning that he can only use his right hand for a while. Help him with some issues he has.

Misof needs to do some tasks. Each of the tasks has to be done during a specific time interval, and it requires constant use of his only hand. Find out whether he can do all the tasks.

You are given the int[]s tStart and tEnd, each with N elements. For each i between 0 and N-1, inclusive, tStart[i] is the timestamp of the beginning and tEnd[i] the timestamp of the end of task i.

(All timestamps are in seconds, with timestamp 0 being the midnight today.)

For each task, Misof needs his hand for the entire interval of time, including both endpoints. That is, if one task ends exactly at the same time at which another task begins, Misof cannot do both of them.

Return "possible" (quotes for clarity) if Misof can do all the tasks and "impossible" if he cannot do that.

Definition

Class:
OneHandScheduling
Method:
checkSchedule
Parameters:
int[], int[]
Returns:
String
Method signature:
String checkSchedule(int[] tStart, int[] tEnd)
(be sure your method is public)

Notes

  • You are not given the value N explicitly. Instead, you can determine it by looking at the number of elements in tStart (or tEnd).
  • Note that the return value is case-sensitive.

Constraints

  • N will be between 1 and 10, inclusive.
  • tStart and tEnd will each contain exactly N elements.
  • Each element of tStart and tEnd will be between 0 and 1,000,000, inclusive.
  • For each i, tStart[i] will be less than tEnd[i].

Examples

  1. {10, 100, 236}

    {47, 235, 347}

    Returns: "possible"

    Task 0 starts at timestamp 10 and ends at timestamp 47. Task 1 starts at timestamp 100 and ends at timestamp 235. Task 2 starts at timestamp 236 and ends at timestamp 347. Misof can do all of them.

  2. {100, 236, 10}

    {235, 347, 47}

    Returns: "possible"

    The same three tasks as in Example #0, just given in another order. The answer remains the same.

  3. {10, 20}

    {20, 30}

    Returns: "impossible"

    These two tasks overlap, so Misof cannot do both of them.

  4. {10, 400000, 500000}

    {20, 600000, 700000}

    Returns: "impossible"

  5. {1, 40, 50, 60}

    {1000000, 41, 51, 61}

    Returns: "impossible"

  6. {451082, 580533, 475708, 598517, 360154, 269932}

    {459478, 586867, 482138, 599188, 367012, 270320}

    Returns: "possible"

  7. {276621, 988439}

    {277608, 988458}

    Returns: "possible"

  8. {448475, 241221, 249290, 548687, 538918, 376524}

    {506438, 272947, 253650, 622212, 587961, 422852}

    Returns: "impossible"

  9. {584885, 603039, 798908, 205503, 250210, 826916, 881458, 764568, 36992, 131595}

    {606770, 609459, 822687, 243406, 275349, 860229, 916856, 781138, 43356, 174116}

    Returns: "impossible"

  10. {886702, 351125, 229170, 493910}

    {901140, 405738, 308424, 540185}

    Returns: "possible"

  11. {848416, 582238, 966795, 274296, 374282}

    {865872, 600765, 968110, 290154, 384513}

    Returns: "possible"

  12. {272885, 765681, 544629, 838456, 231669, 635798, 119470, 657884, 882305, 217145}

    {297780, 797493, 561219, 878009, 268241, 645577, 148561, 658880, 893466, 252993}

    Returns: "impossible"

  13. {278658, 536068}

    {288858, 545028}

    Returns: "possible"

  14. {383336, 796056, 34793, 637314, 277886, 675588, 638199, 542078}

    {427515, 826977, 81205, 679148, 330215, 696232, 692564, 543536}

    Returns: "impossible"

  15. {221631, 362769, 452604, 908921, 725393, 192954, 185259, 492613, 965701, 208327}

    {230012, 369219, 461561, 931469, 751107, 200038, 202749, 521706, 965731, 216348}

    Returns: "impossible"

  16. {387185, 21728, 277083, 43731, 147260, 189980, 775049}

    {395569, 29773, 280379, 51837, 155916, 197412, 784284}

    Returns: "possible"

  17. {728797, 77432, 183629, 876371, 157881, 966637, 569842, 354777, 666396, 909209}

    {728989, 78393, 183880, 877923, 158386, 966728, 570205, 356017, 666617, 911454}

    Returns: "possible"

  18. {642411, 940028, 769671, 560870, 158549}

    {660432, 959026, 794655, 569821, 178832}

    Returns: "possible"

  19. {590305, 515117, 359363, 583555, 54717, 120161, 433562, 437933, 370926, 950647}

    {595267, 524363, 367379, 593348, 57006, 121202, 441884, 439852, 378484, 961345}

    Returns: "impossible"

  20. {455693, 849004, 591323, 547487, 800497, 69406, 819583, 827562}

    {456872, 852215, 594210, 549495, 802555, 69874, 822676, 828567}

    Returns: "possible"

  21. {175025, 485030, 23691, 616272, 102955, 703527}

    {205137, 515212, 41831, 658087, 138667, 705086}

    Returns: "possible"

  22. {864134, 712612, 300998, 42872, 809295, 276049, 568593, 506129, 402342}

    {866378, 736285, 326754, 46445, 826363, 299284, 587927, 525755, 417983}

    Returns: "possible"

  23. {829199, 379545, 606560, 326838, 432113, 807391, 715974, 214821, 767938}

    {912105, 391531, 620019, 393999, 472090, 860486, 759589, 285468, 815140}

    Returns: "impossible"

  24. {896356, 652660}

    {908546, 659642}

    Returns: "possible"

  25. {366772, 611145, 907171, 59219, 970679, 410892}

    {371966, 617757, 909366, 61303, 972405, 413266}

    Returns: "possible"

  26. {892385, 693447, 860853, 857489}

    {912014, 722627, 922133, 908326}

    Returns: "impossible"

  27. {906811, 707258, 57431, 162819, 608474, 503001, 645, 28860}

    {934516, 737235, 91525, 191516, 648717, 519892, 19911, 35578}

    Returns: "possible"

  28. {978738, 177993, 443639, 353009, 521696}

    {992698, 185678, 460133, 369827, 530318}

    Returns: "possible"

  29. {24187, 638466, 705765, 915825, 397746, 897406}

    {84720, 711646, 729293, 965242, 403356, 921214}

    Returns: "impossible"

  30. {654186, 81718, 508511, 430984, 63198, 235321, 484151, 184455, 626983, 417221}

    {654333, 102180, 513069, 455339, 65584, 253678, 496902, 184480, 639579, 433583}

    Returns: "impossible"

  31. {391328, 766115, 128434, 536081, 419936, 107067, 90216, 827849}

    {446417, 820111, 200590, 549747, 500846, 129983, 155565, 890214}

    Returns: "impossible"

  32. {868905, 98277, 414715, 549996, 530199, 343300, 453591, 785311}

    {894680, 139747, 466766, 559773, 547568, 407214, 497246, 799053}

    Returns: "impossible"

  33. {829428, 97212, 374505, 31177, 413712}

    {870369, 102542, 413929, 45873, 447516}

    Returns: "impossible"

  34. {270196, 747915, 899632, 800970}

    {310380, 813460, 914540, 809156}

    Returns: "impossible"

  35. {185878, 511991, 729356, 253033, 424008}

    {265914, 574128, 730284, 330249, 476382}

    Returns: "impossible"

  36. {655693, 581310, 392272, 840079, 825731, 111898, 354261, 67415, 164705, 618534}

    {659163, 589142, 419948, 868439, 831735, 114519, 358905, 84290, 170215, 642088}

    Returns: "possible"

  37. {97191, 132068, 617727}

    {103643, 137775, 619723}

    Returns: "possible"

  38. {575934, 671651, 230209, 712076, 363768, 805969, 94476}

    {596523, 678331, 232555, 725303, 400409, 814848, 116117}

    Returns: "possible"

  39. {806084, 750149}

    {834197, 783325}

    Returns: "possible"

  40. {789475, 807200, 713092, 369259, 836234, 546647, 544714, 446168, 668835}

    {847032, 864353, 767240, 433571, 839207, 572182, 587501, 452600, 725003}

    Returns: "impossible"

  41. {810916, 611112}

    {819045, 617423}

    Returns: "possible"

  42. {774664, 61878, 349914, 826045, 791280, 196581}

    {827960, 105714, 376704, 856769, 839871, 230526}

    Returns: "impossible"

  43. {541504, 125327, 240584, 208255, 657825, 27661, 566148, 517550}

    {584131, 143941, 329110, 229728, 695715, 37176, 572304, 596801}

    Returns: "impossible"

  44. {673113, 647375, 894103, 701838, 6608}

    {675212, 650199, 895678, 706389, 8370}

    Returns: "possible"

  45. {140100, 212229, 469132, 646127, 36216, 835133}

    {188708, 231996, 508627, 690005, 55850, 862775}

    Returns: "possible"

  46. {884563, 438631}

    {907338, 488228}

    Returns: "possible"

  47. {47600, 759226, 592390, 756800, 722937, 956187, 514634, 240884}

    {65333, 785803, 596223, 758373, 748701, 968688, 541983, 264926}

    Returns: "possible"

  48. {361917, 757665, 909517, 654971, 929149, 658079, 355470, 462642, 908049}

    {363028, 758738, 917270, 659343, 930204, 660738, 358825, 466369, 914965}

    Returns: "impossible"

  49. {311126, 6227, 119733, 633878, 591832, 854131, 12439, 263303}

    {328605, 13207, 137176, 646090, 607267, 861152, 23332, 276426}

    Returns: "impossible"

  50. {677871}

    {754742}

    Returns: "possible"

  51. {850335, 843437, 563714, 361470, 938607, 7845, 114596}

    {851683, 863817, 566899, 401380, 952939, 42202, 154699}

    Returns: "impossible"

  52. {914223}

    {918767}

    Returns: "possible"

  53. {402072, 936445, 800139, 486578, 200245, 94133, 290723, 986754, 707910, 975551}

    {407281, 943713, 803379, 490758, 203095, 94443, 297987, 987289, 710401, 980478}

    Returns: "possible"

  54. {639849, 961335, 463207, 485921, 426527}

    {645818, 967236, 465932, 491816, 427264}

    Returns: "possible"

  55. {391642, 102995, 742712, 395724, 395807}

    {403204, 122374, 744665, 397722, 433498}

    Returns: "impossible"

  56. {1 }

    {3 }

    Returns: "possible"

  57. {1, 40, 50, 60 }

    {1000000, 41, 51, 61 }

    Returns: "impossible"

  58. {1, 0 }

    {5, 4 }

    Returns: "impossible"

  59. {3, 2, 1 }

    {4, 5, 6 }

    Returns: "impossible"

  60. {10, 5 }

    {20, 21 }

    Returns: "impossible"

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: