Algorithm to find number of babysitters in $O(n)$ time

Question

I want to hire a babysitter to watch over my baby 24 hours a day. I've gotten $n$ responses. Assume that all 24 hours can be covered. A babysitter is willing to work any part or parts of their availability. Each babysitter is asking for a different pay of $p$ dollars per hour spent watching over the baby. What is an efficient algorithm in $O(n)$ where I can find the times of the day where a new babysitter comes in, paying the cheapest amount to hire all babysitters?

I've tried to sort the babysitters by starting time but the runtime would go to $O(n\log n)$, was wondering if there was a better way to run this in linear time.

Answer 1

For each hour, loop over all $n$ babysitters to find the cheapest available for that hour. $O(24n)=O(n)$.

---

Alternatively, take babysitters as the outer loop, and record the available times for which the current babysitter under consideration is cheaper than the incumbent.

Answer 2

Let's assume that the babysitters do not have their start and end times necessarily on the hour, and suppose we had an algorithm A that solves the problem in this case. I claim that we can use A to solve the sorting problem. Given positive integers $x_1,\ldots,x_n$, we want to sort them. Choose an integer $N > \sum_{i=1}^n x_i$. Let's say now that for each $i$, $1 \leq i \leq n$, that babysitter $i$ has a rate of $N-x_i$, and offers services from time $x_i/n \cdot 24$ to time $24$. Let's also consider an additional $0$th baby sitter which has rate $N$ and offers services for the whole $24$ hours. Using the algorithm, we'll find that the babysitters we use, in chronological order, have decreasing rates, and thus are increasing order in terms of their associated integers. Thus we've solved sorting in linear time plus the time of $A$. Under the normal model of computation, this forces the runtime of $A$ to be $\Omega(n \log n)$ since sorting can't be solved faster than $\theta(n \log n)$.

If the number of starting and end times possible is finite, then this changes, and there is a linear time algorithm. What you do is make an array indexed by possible start/end times. Run through the babysitters and mark a start and end time at the appropriate place in the array. Then walk through the array, and at each point when a baby sitter ends/begins availability, update the optimal babysitter at that point. The time for walk is $O(n)$ since over the whole walk, you consider each baby sitter only twice, when they begin availability or when they end availability.