Real time scheduling with a budget: Parametric-search is better than binary search

We are given a set of jobs each has a processing time, a non-negative weight, a set of possible time intervals in which it can be processed and a cost. The goal is to schedule a feasible subset S of the jobs on a single machine such that the total weight of S is maximized, and the total cost of S is within a given budget. Using Megiddo's parametric method we improve an earlier algorithm that is based on applying binary search.