![subject](/tpl/images/cats/informatica.png)
Computers and Technology, 12.03.2021 15:30 andrespacheco5888
Suppose we have a number of events mi. Each event starts at time si and finishes at time ei, where 0 <= si <= e. We represent the event mi with the closed interval [si, ei]. Our goal is to construct a maximum size set of events, where no two events in the set overlap (note that two events mi and mj where mi = [., x] and mj = [x, .] are not considered to overlap).
Suppose the following intervals are provided.
Event Index Interval
A [1,4]
B [2,3]
C [3,6]
D [5, 9]
E [7,11]
Required:
a. Give the optimal set of events for this example set of intervals.
b. Consider the following greedy approach: at each step, select the event with the earliest starting time that does not conflict with any event already in our set. Show that this approach is not optimal by providing the greedy solution generated by this approach for the above example intervals.
c. Consider a second greedy approach: first order the events by length. Then, at each step, select the event with the shortest length that does not conflict with any event already in our set. While this approach generates the optimal set for the above example, it is not guaranteed to do so for this problem generally. Give a set of 5 intervals for which this second greedy approach fails to generate the optimal solution. Explicitly state both the optimal solution and the solution generated by this approach for your example.
d. State a greedy approach to this problem that always finds the optimal solution.
![ansver](/tpl/images/cats/User.png)
Answers: 2
Another question on Computers and Technology
![question](/tpl/images/cats/informatica.png)
![question](/tpl/images/cats/informatica.png)
Computers and Technology, 23.06.2019 15:00
In the blank libreoffice writer document, to start the process of entering a date field into a letter, click on the insert menu. edit menu. file menu. fields menu.
Answers: 3
![question](/tpl/images/cats/informatica.png)
Computers and Technology, 23.06.2019 18:30
List 3 items that were on kens resume that should have been excluded
Answers: 1
![question](/tpl/images/cats/informatica.png)
Computers and Technology, 24.06.2019 02:00
Which steps will open the system so that you can enter a question and do a search for
Answers: 1
You know the right answer?
Suppose we have a number of events mi. Each event starts at time si and finishes at time ei, where 0...
Questions
![question](/tpl/images/cats/fizika.png)
Physics, 24.07.2019 04:30
![question](/tpl/images/cats/mat.png)
![question](/tpl/images/cats/fizika.png)
![question](/tpl/images/cats/istoriya.png)
![question](/tpl/images/cats/istoriya.png)
![question](/tpl/images/cats/mat.png)
![question](/tpl/images/cats/mat.png)
![question](/tpl/images/cats/health.png)
Health, 24.07.2019 04:30
![question](/tpl/images/cats/istoriya.png)
![question](/tpl/images/cats/en.png)
English, 24.07.2019 04:30
![question](/tpl/images/cats/mat.png)
![question](/tpl/images/cats/istoriya.png)
![question](/tpl/images/cats/mat.png)
Mathematics, 24.07.2019 04:30
![question](/tpl/images/cats/istoriya.png)
![question](/tpl/images/cats/mat.png)
Mathematics, 24.07.2019 04:30
![question](/tpl/images/cats/biologiya.png)
Biology, 24.07.2019 04:30
![question](/tpl/images/cats/himiya.png)
![question](/tpl/images/cats/fizika.png)
![question](/tpl/images/cats/istoriya.png)
History, 24.07.2019 04:30