CSES Solutions – Movie Festivals
In a movie festival, N movies will be shown. You know the starting and ending time of each movie given as movies[][] such that movies[i][0] = starting time of ith movie and movies[i][1] = ending time of ith movie. What is the maximum number of movies you can watch entirely?
Note: If you watch a movie having ending time = T, then you can start watching any other movie whose starting time >= T.
Examples:
Input: N = 3, movies[][] = {{3, 5}, {4, 9}, {5, 8}}
Output: 2
Explanation: You can watch the first and the third movie, that is {3, 5} and {5, 8}.Input: N = 3, movies[][] = {{1, 2}, {2, 3}, {4, 5}}
Output: 3
Explanation: You can watch the first, second and third movie, that is {1, 2}, {2, 3} and {4, 5}.
Approach: To solve the problem, follow the below idea:
The problem can be solved by sorting the movies in ascending order according to the ending times. We can start from the movie with the earliest ending and watch it. Then continue moving to all the movies according to their ending times. For every subsequent movie, check if we can watch it or not. If we can watch it, then move till we find another movie whose starting time >= the current movie’s ending time. After traversing through all the movies, return the final answer.
Step-by-step algorithm:
- Sort the movies according to their ending times.
- Maintain a variable, say moviesWatched to store the total number of movies watched.
- Maintain a variable, say timeElapsed to keep track of the total time elapsed while watching movies.
- Now for each movie, check if we can watch this movie, that is starting time of the movie >= timeElapsed.
- If we can watch the movie, then we increment the count of movies watched as well as the time elapsed.
- If we cannot watch the movie, then we move to the next movie.
- Return the final answer as stored in moviesWatched.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h> using namespace std; // comparator function to sort the vector of pairs movies[] // according to the second value of the pairs (ending time) bool sortFnc(pair< int , int >& p1, pair< int , int >& p2) { return p1.second < p2.second; } // function to calculate the maximum number of movie we can // watch int solve(vector<pair< int , int > >& movies, int N) { // sort the movies according to the ending time sort(movies.begin(), movies.end(), sortFnc); // Variable to track the time elapsed and the number of // movies watched int timeElapsed = 0, moviesWatched = 0; for ( int i = 0; i < N; i++) { // If the current movie starts after the time // elapsed so far, then we can watch it if (movies[i].first >= timeElapsed) { moviesWatched++; timeElapsed = movies[i].second; } } // return the total number of movies watched return moviesWatched; } int main() { // Sample Input int N = 3; vector<pair< int , int > > movies = { { 3, 5 }, { 4, 9 }, { 5, 8 } }; cout << solve(movies, N) << "\n"; return 0; } |
Java
/*code by flutterfly*/ import java.util.*; //defining a pair class class Pair<X, Y> { public final X key; public final Y value; public Pair(X key, Y value) { this .key = key; this .value = value; } public X getKey() { return key; } public Y getValue() { return value; } } public class Main { // Comparator function to sort the ArrayList of pairs movies // according to the second value of the pairs (ending time) static class SortFnc implements Comparator<Pair<Integer, Integer>> { public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) { return p1.getValue() - p2.getValue(); } } // Function to calculate the maximum number of movies we can watch static int solve(ArrayList<Pair<Integer, Integer>> movies, int N) { // Sort the movies according to the ending time Collections.sort(movies, new SortFnc()); // Variables to track the time elapsed and the number of movies watched int timeElapsed = 0 , moviesWatched = 0 ; for ( int i = 0 ; i < N; i++) { // If the current movie starts after the time elapsed so far, then we can watch it if (movies.get(i).getKey() >= timeElapsed) { moviesWatched++; timeElapsed = movies.get(i).getValue(); } } // Return the total number of movies watched return moviesWatched; } public static void main(String[] args) { // Sample Input int N = 3 ; ArrayList<Pair<Integer, Integer>> movies = new ArrayList<>(); movies.add( new Pair<>( 3 , 5 )); movies.add( new Pair<>( 4 , 9 )); movies.add( new Pair<>( 5 , 8 )); System.out.println(solve(movies, N)); } } |
C#
//code by flutterfly using System; using System.Collections.Generic; using System.Linq; public class Program { // Comparator function to sort the list of tuples movies[] // according to the second value of the tuples (ending time) static int SortFnc(( int , int ) p1, ( int , int ) p2) { return p1.Item2.CompareTo(p2.Item2); } // Function to calculate the maximum number of movies we can watch static int Solve(List<( int , int )> movies) { // Sort the movies according to the ending time movies.Sort(SortFnc); // Variables to track the time elapsed and the number of movies watched int timeElapsed = 0, moviesWatched = 0; foreach ( var movie in movies) { // If the current movie starts after the time elapsed so far, then we can watch it if (movie.Item1 >= timeElapsed) { moviesWatched++; timeElapsed = movie.Item2; } } // Return the total number of movies watched return moviesWatched; } public static void Main( string [] args) { // Sample Input List<( int , int )> movies = new List<( int , int )> { (3, 5), (4, 9), (5, 8) }; // Calculate and print the result Console.WriteLine(Solve(movies)); } } |
Javascript
//code by flutterfly // Comparator function to sort the array of pairs movies[] // according to the second value of the pairs (ending time) function sortFnc(p1, p2) { return p1[1] - p2[1]; } // Function to calculate the maximum number of movies we can watch function solve(movies) { // Sort the movies according to the ending time movies.sort(sortFnc); // Variables to track the time elapsed and the number of movies watched let timeElapsed = 0; let moviesWatched = 0; for (let i = 0; i < movies.length; i++) { // If the current movie starts after the time elapsed so far, then we can watch it if (movies[i][0] >= timeElapsed) { moviesWatched++; timeElapsed = movies[i][1]; } } // Return the total number of movies watched return moviesWatched; } // Main function function main() { // Sample Input const movies = [ [3, 5], [4, 9], [5, 8] ]; // Calculate and print the result console.log(solve(movies)); } // Call the main function main(); |
Python3
# code by flutterfly # Function to sort the movies according to the second value of the pairs (ending time) def sortFnc(p): return p[ 1 ] # Function to calculate the maximum number of movies we can watch def solve(movies): # Sort the movies according to the ending time movies.sort(key = sortFnc) # Variables to track the time elapsed and the number of movies watched timeElapsed = 0 moviesWatched = 0 for movie in movies: # If the current movie starts after the time elapsed so far, then we can watch it if movie[ 0 ] > = timeElapsed: moviesWatched + = 1 timeElapsed = movie[ 1 ] # Return the total number of movies watched return moviesWatched def main(): # Sample Input movies = [( 3 , 5 ), ( 4 , 9 ), ( 5 , 8 )] # Calculate and print the result print (solve(movies)) if __name__ = = "__main__" : main() |
2
Time Complexity: O(N * logN), where N is the total number of movies.
Auxiliary Space: O(N)
Contact Us