FastPrepMinimum Machines for Tasks
Problems/Minimum Machines for Tasks

Minimum Machines for Tasks

Expedia logoExpedia● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report gives this task in full, with one example, which is Example 1 here. Each task runs from its start time through its end time, both included, and you want the fewest machines when a machine runs one task at a time.

The report gives no limits and does not say if a task can start and end at the same time. Here, it can, and the start time is never after the end time. The limits and the other examples are our choices, not from the report.

Our version is about 95% the same as the reported question.

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 6 and a task that starts at time 6 both run at time 6, so they cannot use the same machine.
  • A task that ends at time 7 and a task that starts at time 8 share 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[]) → int

Examples

Example 1

start = [1,8,3,9,6]end = [7,9,6,14,7]return = 3

At 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 = 1

The 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 = 2

The 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 = 3

Every 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 = 2

The 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 == n
  • 1 <= n <= 10^5
  • 1 <= 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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int getMinMachines(int[] start, int[] end) {
        // Write your code here.
    }
}
Checking account…