PROBLEM LINK:
Author: Najiba Halim
Tester: Amitkumar Jha
Editorialist: Najiba Halim
DIFFICULTY:
easy-medium
PROBLEM:
Given total number of assignments with their deadlines and marks, find a sequence that will help james get maximum marks. Given total number of assignments with their deadlines and marks, find a sequence that will help james get maximum marks.
SOLUTION 1:
Obtain a permutation of all the possible sequences in which James can do the assignments and calulate the marks in each case. Output the sequence with maximum marks.
This can be done in polynomial time complexity.
SOLUTION :
The above problem is formulation of Job Sequencing algorithm of The Greedy approach.
Where:
tasks = assignments,
And profit= marks.
You can find the explanation here:
The time complexity now will be O(n2) which is enough to pass the given constraints.