Minimum Machines for Tasks
Updated
Problem statement
You have n tasks, given as two integer arrays start and end. Task i runs from time start[i] through time end[i]. Both of those times are part of the task.
Each task runs on one machine, and a machine can only run one task at a time.
- Two tasks that share any time need different machines. A task that ends at time
6and a task that starts at time6both run at time6, so they cannot use the same machine. - A task that ends at time
7and a task that starts at time8share no time, so they can use the same machine. - A task can start and end at the same time. It still needs a machine at that time.
- The tasks can be listed in any order.
Return the smallest number of machines that can run all the tasks.
Function
getMinMachines(start: int[], end: int[]) → intExamples
Example 1
start = [1,8,3,9,6]end = [7,9,6,14,7]return = 3At time 6, the tasks (1, 7), (3, 6), and (6, 7) are all running, because a task's start and end times both count. So you need at least 3 machines.
3 machines are enough:
- Machine 1 runs
(1, 7), then(8, 9). - Machine 2 runs
(3, 6), then(9, 14). - Machine 3 runs
(6, 7).
Example 2
start = [3,1]end = [4,2]return = 1The first task runs from time 3 through 4. The second runs from time 1 through 2. They share no time, so one machine can run the second task and then the first.
Example 3
start = [1,5]end = [5,9]return = 2The first task ends at time 5 and the second starts at time 5. Both run at time 5, so they need different machines.
Example 4
start = [4,4,4]end = [4,4,9]return = 3Every task runs at time 4, including the two that start and end at that same time. So you need 3 machines.
Example 5
start = [1,2,5]end = [10,3,6]return = 2The task (1, 10) overlaps both of the others, but (2, 3) and (5, 6) do not overlap each other. They can share one machine, so 2 machines are enough.
Constraints
start.length == end.length == n1 <= n <= 10^51 <= start[i] <= end[i] <= 10^9
More Expedia Online Assessment questions
- Balanced NumbersOA · Seen Aug 2026
- REST API: Discounted PriceOA · Seen Aug 2026
- Maximum Team SizeOA · Seen Mar 2026
- Per-Domain Request LimiterOA · Seen Oct 2025
- Count Equal-Frequency SubsequencesOA · Seen Mar 2025
- Count Increasing Stock PeriodsOA · Seen Mar 2025
- Get Minimum StepsOA · Seen Oct 2024
- Rank Songs by PopularityOA · Seen Oct 2024
- Calculate the SumOA · Seen Oct 2024
- Get Maximum EfficiencyOA · Seen Oct 2024
Similar questions at other companies
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Latest Arrival to Catch a BusAutodesk · OAAutodesk interview questions
- Minimum Removals to Balance ArraySalesforce · OASalesforce interview questions
- Minimum Markers to Clear Line SegmentsHSBC · OAHSBC interview questions
- Find Minimum Possible SizeMathWorks · OAMathWorks interview questions
- Minimum Days to Watch All MoviesAdobe · OAAdobe interview questions
- Most Disjoint Intervals From Starts and DurationsDocuSign · OADocuSign interview questions
- University Career FairRoblox · OARoblox interview questions
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Can Every Package Fit in a BoxIMC Trading · OAIMC Trading interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)