Posts Finish Maximum Jobs
Post
Cancel

Finish Maximum Jobs

Problem Description

There are N jobs to be done, but you can do only one job at a time.
Given an array A denoting the start time of the jobs and an array B denoting the finish time of the jobs.
Your aim is to select jobs in such a way so that you can finish the maximum number of jobs.

Return the maximum number of jobs you can finish.

Solution

If there are two tasks A and B, such that endTime of A is more than endTime of B. It would make sense to choose B because then we will have more time remaining to complete other tasks.

__A___
B
_______

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class Solution {
    public int solve(ArrayList<Integer> A, ArrayList<Integer> B) {

        List<Pair> list = new ArrayList<>();

        for(int i=0; i<A.size(); i++){
            list.add(new Pair(A.get(i), B.get(i)));
        }

        //Sort based on comparator which uses endTime (ascending order)
        Collections.sort(list);
        
        //If there are no tasks, return 0
        if(list.size() == 0) return 0;

        //At least 1 task is there. Initialize it as the lastTask (this will be the task which has the least endTime)
        //In order words, it will be the task which finishes up the earliest
        int count = 1;
        Pair lastTask = new Pair(list.get(0).startTime, list.get(0).endTime);

        for(int i=1; i<list.size(); i++){
            
            Pair p = list.get(i);

            //If the next task has some overlap with the last task which was done, skip it.
            //Otherwise increase the count and update lastTask
            if(!isOverlapping(lastTask, p)){
                count++;
                lastTask = p;
            }

        }

        return count;
    }

    public boolean isOverlapping(Pair p1, Pair p2){
        //If the startTime of the currentTask if after endTime of previous task => no overlap
        if(p2.startTime >= p1.endTime) return false;
        return true;

    }

}

class Pair implements Comparable<Pair>{
    int startTime;
    int endTime;
    
    Pair(int s, int e){
        startTime = s;
        endTime = e;
    }

    @Override
    //This will be used to sort the Pairs based on endTime
    public int compareTo(Pair a){
        if(this.endTime > a.endTime) return 1;
        else if(this.endTime == a.endTime) return 0;
        else return -1;
    }

    @Override
    public String toString(){
        return "Start: " + this.startTime + " EndTime: " + this.endTime;
    }

}
This post is licensed under CC BY 4.0 by the author.