Problem

You are given a list of jobs to be done, where each job is represented by a start time and end time. Two jobs are compatible if they don’t overlap. Find the largest subset of compatible jobs.

For example, given the following jobs (there is no guarantee that jobs will be sorted):

1
2
3
4
5
6
7
8

[(0, 6),
(1, 4),
(3, 5),
(3, 8),
(4, 7),
(5, 9),
(6, 10),
(8, 11)]

Return:

1
2
3

[(1, 4),
(4, 7),
(8, 11)]

Examples

Example 1

1
2
3

Input: [(0, 6), (1, 4), (3, 5), (3, 8), (4, 7), (5, 9), (6, 10), (8, 11)]
Output: [(1, 4), (4, 7), (8, 11)]
Explanation: The largest compatible subset is jobs that do not overlap.

Example 2

1
2
3

Input: [(1, 3), (2, 5), (4, 6), (6, 7), (5, 8)]
Output: [(1, 3), (4, 6), (6, 7)]
Explanation: The largest compatible subset is jobs that do not overlap.

Example 3

1
2
3

Input: [(1, 2), (2, 3), (3, 4), (4, 5)]
Output: [(1, 2), (2, 3), (3, 4), (4, 5)]
Explanation: All jobs are compatible and can be selected.

Example 4

1
2
3

Input: [(1, 10), (2, 3), (4, 5), (6, 7)]
Output: [(2, 3), (4, 5), (6, 7)]
Explanation: The job (1, 10) overlaps with all others, so the largest compatible subset is the rest.

Example 5

1
2
3

Input: []
Output: []
Explanation: No jobs, so no subset exists.

Solution

Method 1 – Greedy by Earliest End Time

Intuition

This is the classic interval scheduling problem. The key idea is to always pick the job that ends earliest, then skip overlapping jobs. This greedy approach guarantees the largest compatible subset.

Approach

  1. Sort jobs by their end time.
  2. Initialize an empty answer list and a variable to track the end time of the last selected job.
  3. Iterate through jobs:
    • If the job’s start time is at least the end time of the last selected job, add it to the answer and update the end time.
  4. Return the answer list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<pair<int, int>> largestCompatibleJobs(vector<pair<int, int>>& jobs) {
        sort(jobs.begin(), jobs.end(), [](auto& a, auto& b) { return a.second < b.second; });
        vector<pair<int, int>> ans;
        int lastEnd = INT_MIN;
        for (auto& job : jobs) {
            if (job.first >= lastEnd) {
                ans.push_back(job);
                lastEnd = job.second;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func LargestCompatibleJobs(jobs [][2]int) [][2]int {
    sort.Slice(jobs, func(i, j int) bool { return jobs[i][1] < jobs[j][1] })
    ans := make([][2]int, 0)
    lastEnd := -1 << 31
    for _, job := range jobs {
        if job[0] >= lastEnd {
            ans = append(ans, job)
            lastEnd = job[1]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public List<int[]> largestCompatibleJobs(int[][] jobs) {
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[1]));
        List<int[]> ans = new ArrayList<>();
        int lastEnd = Integer.MIN_VALUE;
        for (int[] job : jobs) {
            if (job[0] >= lastEnd) {
                ans.add(job);
                lastEnd = job[1];
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def largest_compatible_jobs(self, jobs: list[tuple[int, int]]) -> list[tuple[int, int]]:
        jobs = sorted(jobs, key=lambda x: x[1])
        ans = []
        last_end = float('-inf')
        for job in jobs:
            if job[0] >= last_end:
                ans.append(job)
                last_end = job[1]
        return ans

Complexity

  • ⏰ Time complexity: O(n log n)
    • Sorting jobs by end time dominates.
  • 🧺 Space complexity: O(n)
    • Output list and sorting.