Task 1 — Weighted Interval Scheduling

Objective

Given a collection of jobs, select a subset of non-overlapping jobs whose total value is maximal.

Each job has:

ID
Start
End
Value

Two jobs are compatible when their time intervals do not overlap.

Job Model

A possible model is:

type Job struct {
    ID    string
    Start int
    End   int
    Value int
}

The interval uses:

[start, end)

semantics.

This means:

Job A: [2, 5)
Job B: [5, 8)

do not overlap.

Input

Use the following jobs:

J01: Start=1,  End=4,  Value=20
J02: Start=3,  End=5,  Value=25
J03: Start=0,  End=6,  Value=40
J04: Start=4,  End=7,  Value=30
J05: Start=3,  End=9,  Value=45
J06: Start=5,  End=9,  Value=50
J07: Start=6,  End=10, Value=35
J08: Start=8,  End=11, Value=40
J09: Start=8,  End=12, Value=60
J10: Start=11, End=14, Value=30
J11: Start=12, End=15, Value=50
J12: Start=13, End=16, Value=55

Required Function

Create a function conceptually equivalent to:

func FindBestSchedule(jobs []Job) ScheduleResult

A possible result model is:

type ScheduleResult struct {
    Jobs       []Job
    TotalValue int
}

Rules

The selected jobs must satisfy:

no selected jobs overlap

and:

sum of selected job values is maximal

The result should return the selected jobs ordered by start time.

Example Reasoning

Consider:

J01: [1,4) Value=20
J04: [4,7) Value=30
J09: [8,12) Value=60
J12: [13,16) Value=55

These jobs do not overlap.

Their total value is:

20 + 30 + 60 + 55 = 165

However, the implementation must evaluate all relevant alternatives and determine whether a better valid schedule exists.

Do not assume that this example is optimal.

Compatibility

For every job, determine which earlier job is the latest compatible job.

Conceptually:

PreviousCompatible[i]

contains the index of the latest job whose:

End <= Current.Start

This relationship may be useful for dynamic programming.

Dynamic Programming Interpretation

For a job i, the optimal solution may either:

exclude job i

or:

include job i

If included, its value is combined with the best compatible solution before it.

Conceptually:

best[i] =
    max(
        best[i-1],
        jobs[i].Value + best[previousCompatible[i]]
    )

The exact implementation is your choice.

Tie-Breaking

If several schedules have the same maximum total value:

1. prefer the schedule with fewer jobs
2. if still equal, compare selected job IDs lexicographically

Example:

[J01, J05]

is preferred over:

[J02, J04, J06]

when both have the same total value and the first uses fewer jobs.

Validation

Reject or report invalid jobs where:

ID is empty
Start < 0
End <= Start
Value < 0
duplicate ID exists

Edge Cases

Test:

empty input
single job
all jobs overlap
no jobs overlap
zero-value jobs
multiple optimal solutions
jobs touching at interval boundaries

Additional Test Case

Input:

A: [1,3) Value=10
B: [3,5) Value=15
C: [1,5) Value=24
D: [5,7) Value=8

Possible schedules include:

A + B + D = 33
C + D     = 32

Expected result:

A
B
D

with:

TotalValue = 33

Restrictions

Do not use a third-party library that directly solves weighted interval scheduling.

Sorting helpers are allowed.

Goal

This task demonstrates that choosing the individually highest-value job does not necessarily produce the optimal global schedule.

The implementation should separate:

interval compatibility
optimization
solution reconstruction