Consider procedure schedule in the Scheduling with Deadlines algorithm (Algorithm 4.4). Let \(d\) be the maximum of the deadlines for \(n\) jobs. Modify the procedure so that it adds a job as late as possible to the schedule being built, but no later than its deadline. Do this by initializing \(d+1\) disjoint sets, containing the integers \(0,1, \ldots, d\) Let \(\operatorname{small}\) ( \(\mathrm{S}\) ) be the smallest member of set \(\mathrm{S}\). When a job is scheduled, find the set \(S\) containing the minimum of its deadline and \(n\). If small \((S)=0,\) reject the job. Otherwise, schedule it at time \(\operatorname{small}(S),\) and merge \(S\) with the set containing small \((S)-1 .\) Assuming we use Disjoint Set Data Structure III in Appendix \(C\). show that this version is \(\theta(n \lg m)\), where \(m\) is the minimum of \(d\) and \(n\)

Step by step solution

01

Identify Important Aspects

The problem mentions that we are using the Disjoint Set Data Structure III as mentioned in Appendix C. Here, \(d\) is the maximum deadline among all jobs, \(n\) is the total number of jobs, and \(m\) is the minimum of \(d\) and \(n\). The job with the minimum time of either its deadline or \(n\) will be scheduled.

02

Initial Stages of the Algorithm

Initialize \(d+1\) disjoint sets containing integers from \(0\) to \(d\). 'Small' is a function which outputs the smallest member of a set S. Now, schedule a job by finding the set S which contains the minimum of its deadline and \(n\).

03

Middle Stages of the Algorithm

After finding set S, if the smallest member of the set is \(0\), the job is rejected. If it is not, the job is scheduled at the time given by small(S). Then, set S is merged with the set containing small(S)-1.

04

Analyze the Time Complexity

Time complexity of a union operation in disjoint set data structure represented by size can be \(\theta(\lg m)\), where \(m\) is the smallest among \(n\) (number of elements) and \(d\) (maximum deadline). As there are \(n\) jobs and for each job the union operation is performed one time, the time complexity of this scheduling algorithm is \(\theta(n \lg m)\).

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!