Movie marathon - Maximum how many shows one can watch?

[kuldeep sidhu]

The problem is as follows-
there are two arrays one with movie start timings and one with movie end timings..we need to figure out maximum how many movies a person can watch using the given start and end timings.

int movie_start []  = {8,9,1,4,5};
int movie_end []   =  {9,2,3,7,8};

so as per above timings
one can watch maximum of three shows i.e 8-9,9-2,4-7 or 8-9,1-3,4-7

if we need to write a sample program to calculate the no of shows one can watch..how can we achieve that?
i thought of parsing each element of both the arrays and then taking end time of show from movie_end array and checking in movie_start array if show starts after that time and do that recursively..
Please suggest .

[Jayesh A Lalwani]

First.. Your arrays are confusing.Does 8 refer to 8am or 8pm. I am assuming you intend to use a 24 hr clock in your array. SO, it should be

int movie_start []  = {8,9,13,16,17};  
int movie_end []   =  {9,14,15,19,20};  

Second, Are your arrays sorted by start time?

Third, Are you trying to maximize the number of movies, or the amount of time you spent watching movies?

Fourth, what have you tried already? forget about how you will do this in code. How will you do this on paper? You could approach this multiple ways:You could

One way is. FInd the first movie when I'm free. That moves my free time to end of the movie. Then find the next movie when I'm free and so on.. BUT!! It could be that the first movie that I'm free is 3 hours long, and there are 2 back to back 2-hour movies that start when the 3 hour movie starts. So, it's better for me to miss the 3 hour movie and try the next movie. So, what you need is multiple

Or try to watch all movies. Then see if any of the movies collide. If no movies collide, you have your answer. If movies collides, try to remove one movie, and see if it still collides. If nothing collides after removing one movie then you have your answer. If something collides, then put the movie back and remove the next movie. THe problem is if you get collisions even after removing each colliding movie. You have to remove 2 colliding movies. So, you have to repeat the process after removing 2 colliding movies.. and then 3 and then 4..

[fred rosenberger]

side note: parallel arrays like this are a terrible design. They are prone to errors and getting out of sync. Now, you may have been handed this and are stuck with it, but if not, re-design that NOW.

[Rico Felix]

Since you are using an object-oriented programming language it would be better to use the programming style that the language supports...

Although the following is not a suggested template, I would have gone in this direction:

Create a Movie class to represent movie objects that contain movie information:

public class Movie {

	private String title_;
	private int startTime_;
	private int endTime_;

	public Movie(String title, int startTime, int endTime) {
		title_ = title;
		startTime_ = startTime;
		endTime_ = endTime;
	}

	public String getTitle() {
		return (title_);
	}

	public int getStartTime() {
		return (startTime_);
	}

	public int getEndTime() {
		return (endTime_);
	}

	public int getMovieLength() {
		return (endTime_ - startTime_);
	}

}

Create a class to represent the marathon event holding relevant information and methods:

public class MovieMarathon {

	private Movie[] selections_;
	private int index;

	public MovieMarathon(int maxSelections) {
		selections_ = new Movie[maxSelections];
	}

	public boolean addMovie(Movie selection) {

		if (index < selections_.length) {

			for (int i = 0; i < index; i++) {
				if (selection.getTitle().equals(selections_[i].getTitle())) {
					System.out.println(selection.getTitle()
						+ " was already added to your list");
					return (false);
				}
			}

			selections_[index++] = selection;
			return (true);

		} else {
			System.out.println("Your list is currently maxed out");
			return (false);
		}

	}

	public int getTotalWatchTime() {

		int totalWatchingTime = 0;

		for (Movie movie : selections_) {
			totalWatchingTime += movie.getMovieLength();
		}

		return (totalWatchingTime);
	}
}

The following class is just a quick test:

public class Cinema {

	public static void main(String[] args) {

		MovieMarathon mm = new MovieMarathon(3);

		mm.addMovie(new Movie("First Movie", 8, 9));
		mm.addMovie(new Movie("Second Movie", 9, 14));
		mm.addMovie(new Movie("Third Movie", 13, 15));
		mm.addMovie(new Movie("Fourth Movie", 16, 19));

		int timeSpentInCinema = mm.getTotalWatchTime();

		System.out.println("Total time spent in the movie marathon: "
			+ timeSpentInCinema + " hours");
	}
}

The main point is you should consider using object notation to design your application by creating the necessary classes to represent the relevant objects that interact within your system...

[Jayesh A Lalwani]

Rico,

Your algorithm for computing the total watch time is wrong. It doesn;t take into account overlaps between movie times

[Rico Felix]

Jayesh A Lalwani wrote:Rico,

Your algorithm for computing the total watch time is wrong. It doesn;t take into account overlaps between movie times

Thank you for pointing that out as it won't prove to be helpful... Guess I was too eager to make a suggestion

The implementation is also too low level by using arrays I guess

Here is my attempt at providing an improved solution:

Improved Movie class:

public class Movie
{
	private String title;
	private int startTime;
	private int endTime;

	public Movie(String title, int startTime, int endTime) {
		this.title = title;
		this.startTime = startTime;
		this.endTime = endTime;
	}

	public String getTitle() {
		return title;
	}

	public void setTitle(String newTitle) {
		title = newTitle;
	}

	public int getStartTime() {
		return startTime;
	}

	public void setStartTime(int newStartTime) {
		startTime = newStartTime;
	}

	public int getEndTime() {
		return endTime;
	}

	public void setEndTime(int newEndTime) {
		endTime = newEndTime;
	}

	public int getLengthOfMovie() {
		return (endTime - startTime);
	}

	public boolean equals(Object movie) {
		if (movie == null) {
			return false;
		} else if (this == movie) {
			return true;
		} else if ((movie instanceof Movie)
					&& (this.title == ((Movie)movie).title)) {
			return true;
		} else {
			return false;
		}
	}

	public int hashCode() {
		return (title.hashCode() ^ getLengthOfMovie());
	}
}

Improved MovieMarathon class:

import java.util.List;
import java.util.ArrayList;

public class MovieMarathon
{
	private List<Movie> selections;
	private int maxSelections;

	private String movieClash;

	public MovieMarathon(int maxSelections) {
		selections = new ArrayList<Movie>(maxSelections);
		this.maxSelections = maxSelections;
	}

	public boolean addMovie(Movie selection) {
		if (!selections.contains(selection)
			&& !(selections.size() >= maxSelections)) {
			if (isTimeOverlap(selection)) {
				System.out.println(selection.getTitle()
					+ " overlaps with " + movieClash);
				return false;
			}
			selections.add(selection);
			return true;
		} else if (selections.contains(selection)) {
			System.out.println(selection.getTitle() + " was already added");
			return false;
		} else {
			System.out.println("List is maxed out");
			return false;
		}
	}

	public boolean removeMovie(Movie selection) {
		return selections.remove(selection);
	}

	public void displaySelections() {
		System.out.println("Your selections are:");
		for (Movie movie : selections) {
			System.out.println(movie.getTitle());
		}
	}

	private boolean isTimeOverlap(Movie selection) {
		for (Movie movie : selections) {
			if (movie.getEndTime() >= selection.getStartTime()) {
				movieClash = movie.getTitle();
				return true;
			}
		}
		return false;
	}
}

Improved Cinema test class:

import java.util.List;
import java.util.ArrayList;

public class Cinema
{
	public static void main(String[] args) {

		List<Movie> options = new ArrayList<>();
		options.add(new Movie("C Movie", 8, 9));
		options.add(new Movie("C++ Movie", 9, 11));
		options.add(new Movie("C# Movie", 10, 12));
		options.add(new Movie("Java Movie", 8, 9));
		options.add(new Movie("Ruby Movie", 13, 14));

		MovieMarathon mm = new MovieMarathon(3);
		mm.addMovie(options.get(0));
		mm.addMovie(options.get(1));
		mm.addMovie(options.get(3));
		mm.addMovie(options.get(2));
		mm.addMovie(options.get(4));

		mm.displaySelections();
	}
}

I should mention again that this suggestion is not to be taken as a template to use but only as my thoughts on the design path I would have took at implementing the application instead of using arrays which could probably give the OP an insight on a different approach.

[Campbell Ritchie]

Pleased to see the underscores are taken out of the field identifiers.