Skip to content

Using two approaches to solve the job sequencing problem, both approaches use binary search tree and greedy algorithm. Time complexity for two approaches are n log(n).

Notifications You must be signed in to change notification settings

yy-cc-20/Job-Sequencing-Problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

19 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Job-Sequencing-Problem 💼

Given a list of exam and assignments with deadlines and marks, arrange the sequence of doing the tasks to get the maximum marks.

Sample Data

image

Assumptions

  1. A task can be done within one day.
  2. Only able to do one task in a day
  3. Every task can start at any day before its deadline.
  4. The marks will be earned after the task is completed.

Solutions 💡

Approach 1

For each task, choose the day which is the closest to the deadline from list of available days.

Approach 2

For each day, choose the task with the highest marks from list of unassigned tasks.

Used binary search tree and greedy algorithm for both approaches to find the optimal choice for each day/task. Both approaches give the same result.

The time complexity for both algorithm are O(n log(n)). 🌟

Test Case 1: Same Deadline Same Profit

image

Test Case 2: Same Deadline Different Profit

image

Test Case 3: Different Deadline Same Profit

image

Test Case 4: Different Deadline Different Profit

image

Test Case 5: Unable To Finish All The Tasks

image

Test Case 6: Nagtive Values

image

Please ⭐️ this repository if this project helped you!

About

Using two approaches to solve the job sequencing problem, both approaches use binary search tree and greedy algorithm. Time complexity for two approaches are n log(n).

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages