• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • paul wheaton
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Tim Holloway
  • Carey Brown
  • salvin francis

Here is my code for Activity Selection using Greedy Algorithm,Can you please verify it?Thank you

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

 
Saloon Keeper
Posts: 3462
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you copy code into the textarea, then select it (drag the mouse over the code) and then press the 'code' button. If you only press the code button, then in the textarea you will see these tags: , followed by your code that appears as plain text. I corrected it.

Before I comment on your code, one question: what is your intention? Is it to get as many activities as will fit, or do you want to have as many days occupied in the time given? For instance, if you have these activities:

A(2, 3)
A(5, 6)
A(0, 7)

you have now the activities A(2, 3) and A(5, 6), leaving the days 1, 4 and 7 unused. Is that what you intend?
 
Sheriff
Posts: 6187
164
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your classes seem to work fine.  Here are some (maybe picky) notes mostly about style:

Main class:

* Don't forget to show the package and include statements.

* Use the implementation as the declared type if you can.  So instead of

use

* You have two objects named "A3".

* Use for-each loops (also called enhanced for loops) when you can.  Also, you don't need to call the toString() method on an object when you pass it to System.out.println().  So instead of

use

ActivitySelection class:

* You have an unused include:

import java.util.Collections;

* Object names should start with a lowercase letter.

* There is an unnecessary semicolon on its own line.

* Method names should start with a lowercase letter.
 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Knute Snortum
Thank you for your suggestions.

 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Souris

There are n activities given with their start and finish times. We have to Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Souris

There are n activities given with their start and finish times. We have to Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
 
Piet Souris
Saloon Keeper
Posts: 3462
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a few remarks in addition to what Knute remarked.

First of all, you now have it so that there is a static method 'Selection', and an instance method 'compare'. Well, nothing wrong with that, but it looks a bit strange. There is no need to have that class implement 'Comparator<Activity>' though. You could have a Field

, that you could define as:

and have a static method 'getComparator()' that simply returns this comparator.
So, instead of saying: Collections.sort(list, new ActivitySelection()), you could then have Collections.sort(list, ActivitySelection.getComparator());.

There is a danger when returning the difference of two ints as the result of a Comparator, though. The difference might not fit into an int. For instance: Integer.MAX_VALUE - INTEGER.MIN_VALUE does not fit in an int, so your outcome would be wrong. But since finish is always a positive number, it doesn't matter here.

As Knute remarked, try using the interfaces instead of concrete implementations. Take this method:

You can only call this method when you have an ArrayList<Activity>. But that rules out the situations that you have a LinkedList<Activity> or a TreeSet<Activity>. So, change the parameter to at least: List<Activity>.

Your code is working as it should. I would refine my Comparator just a little bit, although it makes no difference. I would have my Activities first compared on their duration, and when that fails, I would then compare on starting day. In modern Comparator speak you could have something like this:
 
Piet Souris
Saloon Keeper
Posts: 3462
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
On second thought: your Comparator is fine. If you use the Comparator that I described, and you have the Activities A(1, 2) A(2, 7), A(8, 9), then you might miss A(2, 7).
 
I do some of my very best work in water. Like this tiny ad:
professionally read, modify and write PDF files from Java
https://products.aspose.com/pdf/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!