Optimal Freelancing

Tags

Optimal Freelancing

Category

Greedy

Difficulty

Easy

Problem Statement

Given a list of freelance jobs, each with a deadline (in days) and a payment, find the maximum profit achievable. Each job takes exactly 1 day to complete, and you can only complete one job per day. You have 7 days available (days 1 through 7). A job with deadline d must be completed on or before day d.

Intuition

To maximize profit, prioritize higher-paying jobs and schedule each one as late as possible before its deadline. Scheduling late preserves earlier time slots for other jobs that may have earlier deadlines. This greedy strategy of processing jobs from highest to lowest payment and assigning each to the latest available slot works because it maximizes the chance that all profitable jobs can be accommodated.

Approach

  1. Sort jobs by payment in descending order.
  2. Create an array of 7 time slots (days 1-7), all initially available.
  3. For each job (in order of decreasing payment):
    • Find the latest available day on or before the job's deadline (capped at 7).
    • If such a day exists, schedule the job there and add its payment to the total profit.
  4. Return the total profit.

Pseudocode

function optimalFreelancing(jobs):
    sort(jobs by payment, descending)
    timeline = array of 7 booleans, all false  // false = available

    profit = 0
    for job in jobs:
        maxDay = min(job.deadline, 7)
        for day from maxDay down to 1:
            if timeline[day - 1] == false:
                timeline[day - 1] = true
                profit = profit + job.payment
                break

    return profit

Time & Space Complexity

  • Time: O(n log n) for sorting the jobs, plus O(n * 7) = O(n) for scheduling since we have at most 7 days. Overall O(n log n).
  • Space: O(1) since the timeline array is fixed at size 7.

Key Insights

  • Sorting by payment ensures we consider the most valuable jobs first.
  • Scheduling as late as possible (latest available slot) is critical: it keeps earlier slots free for jobs with tighter deadlines.
  • The 7-day constraint makes the scheduling step O(1) per job (at most 7 iterations), keeping the algorithm efficient.
  • Jobs with deadlines beyond 7 are effectively treated as having a deadline of 7.

Edge Cases

  • No jobs: profit is 0.
  • All jobs have deadline 1: only the highest-paying job can be completed.
  • Multiple jobs with the same deadline: the highest-paying ones are prioritized.
  • Job deadline exceeds 7: cap it at 7.
  • More jobs than available days: some jobs must be skipped; greedy ensures lowest-paying ones are dropped.
  • All jobs have the same payment: scheduling order does not matter, just fill as many slots as possible.

Linked mentions