Design greedy algorithm to solve activity selection problem

Assignment Help Data Structure & Algorithms
Reference no: EM13326596

Design a greedy algorithm to solve the activity selection problem. Suppose there are a set of activities: a1, a2, ... an that wish to use a lecture hall. Each activity ai has a start time siand a finish time fi. A lecture hall can be used by only one activity at a time. Two activities can be scheduled in the same lecture hall if they are non-conflicting (fi<= sj or fj<= si) Your algorithm should find out the minimum number of lecture halls needed to hold all the activities. Write a program to implement your algorithm. For example: if the activities you need to schedule have the following start times and finish times,


4 7
6 9
7 8
1 3
1 4
2 5
3 7

then the output of your program is "the minimum number of lecture halls required is 3". Also indicate which activity will be scheduled in which lecture hall.

 

Reference no: EM13326596

Questions Cloud

What is her velocity at the bottom of the swing : A gymnast whose mass is 50.0 kg swings back and forth on a 4.0m long rope. What is her velocity at the bottom of the swing
What is the height of the table : What is the gravitational force between two 20-kg iron balls separated by a distance of .9 m? What is the height of the table
Create a work plan : Design a dynamic programming algorithm to find the value of the optimal plan. Implement your algorithm using any programming language you prefer. Describe the recurrence relation used by your algorithm at the top of your program or in a separate f..
Identify the budgetary accounts used in federal agency : Identify the budgetary accounts used in federal agency accounting and explain the sequential flow of budgetary authority through the accounts in your own words.
Design greedy algorithm to solve activity selection problem : Design a greedy algorithm to solve the activity selection problem. Suppose there are a set of activities: a1, a2, ... an that wish to use a lecture hall. Each activity ai has a start time siand a finish time fi.
Evaluate account balances : Shiras Distributing Company had the following account balances - the company completed the following summary transactions.
What is its maximum height above the ground : A gray kangaroo can bound across level ground with each jump carrying it 8.1m from the takeoff point. What is its maximum height above the ground
Implement the boyer-moore algorithm using any program : Implement the Boyer-Moore algorithm using any programming language you prefer.
What is the temperature of the aluminum disk : A thick, vertical iron pipe has an inner diameter of 0.077 m. A thin aluminum (? = 23x10-6 (C°)-1) disk, What is the temperature of the aluminum disk when the disk falls into the pipe

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Creating algorithm to implement function

Create an Algorithm to implement the given function and explain how the required task can be achieved in a step by step process.

  Explain queue crawl through memory in direction of its head

Does queue crawl through memory in direction of its head or its tail? Describe your answer. Describe how lack of metrics for measuring certain software properties affects software engineering discipline.

  What is the best algorithm for sorting

What is the best algorithm for sorting each of the following: general comparable objects, long character strings, double precision floating point numbers, 32-bit integers, and bytes? Justify your answer.

  Professional codes of ethics

Select one of the Professional Codes of Ethics associated with IT. If you were to complete a assignment related to securing the connectivity in your firm and its business partners.

  Scaled and unscaled value of solution that algorithm finds

For each value of ε, give items included and scaled and unscaled value of solution that algorithm finds. For tables, you only require to show those rows which correspond to values less than or equal to scaled value of this solution.

  Dbms and data mining to imporve customer service

Discuss how a database management system and data mining can help motor vehicle maintenance center improve its services, and what tables would be required in such a database.

  Create greedy algorithm to find market to buy apples

Assume we drive pickup truck from city A to city B. Along high way, we will go through n apple markets, labeled with 1, 2, ..., n, where you can buy or sell apples. which means you buy and sell apples at the same market i.

  .specify and define a method for linkedbag

Add a constructor to the class LinkedBag that creates a bag from a given array of entries.Specify and define a method for LinkedBag that removes a random entry from the bag.

  Definition of a method isreverse

Provide the definition of a method, isReverse , whose two parameters are arrays of integers of equal size. The technique returns true if and only if one array is reverse of the other.

  Build b tree for the part table

Build B+ tree for the PART table with n = 6 pointers; illustrate how B+ tree expand (show several intermediate trees) and what final tree will look like.

  Diagram of a telephone network

Consider a diagram of a telephone network, which is a graph G whose vertices represent switching centers, and whose edges represent communication lines joining pairs of centers. Edges are marked by their bandwidth, and the bandwidth of a path is the ..

  One e business failure

Discuss about one e-Business failure. Describe what happened and what you would have done differently. Explain whether or not the e-Business practiced sound financial planning.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd