Distribute items based on the time duration

Question

I just finished a small assignment and I would like to get some feedback about the implementation here. Basically, it was all about distributing items ("talks" in this case) throughout the day based on the time constraints (their duration). For instance, a given place have different "tracks" each of which has a morning (9AM - 12PM) and afternoon (1PM - 5PM) session.

The input data is a file with this structure: Talk Name XYmin (where XY are positive numbers).

This is what I came up with (I know it's a little bit silly but I guess it works for the most part):

public final class Conference {
  private static final long MORNING_SPAN = 180; // 09:00 AM - 12:00PM

  private static final long AFTERNOON_SPAN = 240; // 01:00 PM - 05:00 PM

  private final List<Talk> talks;

  private final List<Track> tracks;

  private final long numberOfTracks;

  public Conference(final List<Talk> talks) {
    final var duration = talks.stream().mapToLong(Talk::duration).sum();
    final var daySpan = MORNING_SPAN + AFTERNOON_SPAN;
    this.talks = talks;
    numberOfTracks = duration / daySpan + (duration % daySpan == 0L ? 0L : 1L);
    tracks = new LinkedList<>();
  }

  public List<Track> getTracks() { return tracks; }

  public void displaySchedule() {
    if (tracks.isEmpty()) {
      makeSchedule();
    }
    // More System.out.println statements for the required output
  }

  private void makeSchedule() { // ...this one is the deal!
    for (int i = 0; i < numberOfTracks; i++) {
      final var morning = new LinkedList<Talk>();
      final var afternoon = new LinkedList<Talk>();
      var morningSpan = MORNING_SPAN;
      var afternoonSpan = AFTERNOON_SPAN;
      final var iterator = talks.iterator();
      while (iterator.hasNext()) {
        final var talk = iterator.next();
        if (talk.duration() <= morningSpan) {
          morning.add(talk);
          morningSpan -= talk.duration();
          iterator.remove();
        } else if (talk.duration() <= afternoonSpan) {
          afternoon.add(talk);
          afternoonSpan -= talk.duration();
          iterator.remove();
        }
      }
      tracks.add(new Track(morning, afternoon));
    }
  }
}

public final class Talk {
  public final String title;

  public final String duration;

  public Talk(final String title, final String duration) {
    this.title = title;
    this.duration = duration;
  }

  public long duration() {
    if ("lightning".equalsIgnoreCase(duration)) {
      return Constant.LIGHTNING;
    }
    // Basically this returns the duration for the talk (as long)...that's it
    return Long.parseLong(Constant.NON_NUMBERS.matcher(duration).replaceAll(""));
  }
}

public final class Track {
  private final List<Talk> morning;

  private final List<Talk> afternoon;

  public Track(final List<Talk> morning, final List<Talk> afternoon) {
    this.morning = morning;
    this.afternoon = afternoon;
  }

  // Some more stuff here to display the required output
}

The real deal here is Conference::makeSchedule — that's where I would like to know if there is a better, more efficient way to approach this solution...probably using different data structures, etc. Thanks in advance!

Answer 1

Nice implementation, it's well structured and easy to understand. Few general suggestions:

• int instead of long: the constants MORNING_SPAN and AFTERNOON_SPAN contain minutes in a day, using an int is enough.
• Input validation: the talk duration needs to be validated. If the talk duration is greater than MORNING_SPAN or AFTERNOON_SPAN it won't be included in any track. If it's negative it will also lead to issues. In the Conference class ensure that the list talks is not empty.
• Creating the schedule: I see that the schedule is created (lazily) in the displaySchedule method of Conference. I think that creating the schedule is an important action, it can be the responsibility of another class, like ScheduleMaker. Then, the list of tracks can be added to Conference in the constructor.
• Talk interface: talk.duration returns a string like "30min", while talk.duration() returns 30 as a long. I find it a bit confusing. If you need both, consider creating two different variables and two getters. Otherwise, parse the duration in the constructor and use only the long value.

Bin packing problem

Let's consider this example:

morning_span = 2m (2 minutes)
afternoon_span = 1m
daily_span = morning_span + afternoon_span = 3m

talk1 = 2m
talk2 = 2m
talk3 = 2m
total_talks_duration = 6m

Calling conference.makeSchedule() will result in:

numberOfTracks = total_talks_duration / daily_span = 6 / 3 = 2

Schedule:
Track1 = talk1 (morning)
Track2 = talk2 (morning)
talk3 ??

As you can see the current makeSchedule will create two tracks, but talk3 won't be included.

This bug can be fixed by running the other loop till all the talks are placed:

private void makeSchedule() {
    while (talks.size() > 0) {
        // Create a new track
        // Add in the track as many talks as possible
        // Remove talks added to the current track
    }
}

Now all talks will be placed in the tracks, however, there are cases where the algorithm will create more tracks than needed. This is considered a Bin packing problem. Basically, fit the talks in the minimum number of tracks. Interestingly, my university professor developed an exact algorithm for this problem (pdf). I'll leave it to you for additional study.