QuestionQuestion

Implement the activity selection last-to-start algorithm. Include a verbal description of your algorithm, pseudocode and analysis of the theoretical running time. You do not need to collected experimental running times.

The program should read input from a file named “act.txt”. The file contains lists of activity sets with number of activities in the set in the first line followed by lines containing the activity number, start time & finish time.
Example act.txt:
11
1 1 4
2 3 5
3 0 6
4 5 7
5 3 9
6 5 9
7 6 10
8 8 11
9 8 12
10 2 14
11 12 16
3
3 1 8
2 1 2
1 3 9

In the above example the first activity set contains 11 activities with activity 1 starting at time 1 and finishing at time 4, activity 2 starting at time 3 and finishing at time 5, etc.. The second activity set contains 3 activities with activity 3 starting at time 1 and finishing at time 8 etc. Note: the activities in the file are not in any sorted order.

Your results including the number of activities selected and their order should be outputted to the terminal. For the above example the results are:

Set 1
Number of activities selected = 4 Activities: 2 4 8 11

Set 2
Number of activities selected = 2 Activities: 2 1

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

public class Activity implements Comparable<Activity>{   
    private int number;
    private int start;
    private int end;
    private boolean selected;

    public Activity(int number, int start, int end) {
       this.number = number;
       this.start = start;
       this.end = end;
       selected = false;
    }

    public int getNumber() {
       return number;
    }

    public int getStart() {
       return start;
    }

    public int getEnd() {
       return end;
    }

    public boolean isSelected() {
       return selected;
    }
   
   
    public void setNumber(int number) {
       this.number = number;
    }

    public void setStart(int start) {
       this.start = start;
    }

    public void setEnd(int end) {
       this.end = end;
    }

    public void setSelected(boolean selected) {
       this.selected = selected;
    }   

    @Override
    public int compareTo(Activity o) {
       if (o == null) {
            return 1;
       }
       return getStart() - o.getStart();
    }
}...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$90.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats