Scheduling Problem (greedy algorithm) | Hello World
Both of the questions is attacked by using the greedy algorithm
First Question:
If you have only one room, what is the maximum number of meetings you can scheduled into that room.
Solution:
1. sort the meetings by finishing time, this is because we greedily choose the meeting that finishes first.
2. go through all the meetings in order of finishing time, schedule the meeting into the room if the room is not occupied at its start time, and increase the count by one.
3. no of count will be the max number of meetings you can schedule into the room.
We need to prove that the greedy algorithm is correct (choosing the meeting that finishes first can result in a optimal solution) assume there is another schedule S' that schedules more meetings (k + 1) then the solution S (k solutions). Then at some point the S' must scheduled some meeting that tm' ends before the tm scheduled by S. But as we know that since S scheduled meeting that finishes first so the mth meeting must finishes no later than mth scheduled by S'. which is a contradiction.
Second Question:
You are given a set of meetings with start time and end time, what is the minimum number of meeting rooms you need to have to hold all the meetings.
The brute force method is to compare every start and end time one by one, and that will take a O(n^2) run time where n is the number of meetings to find out the minimum number of meeting rooms.
A better solution using the greedy approach
1. We sort the meetings by start time
2. Then step through all the meetings in order of start time, keep a set of meeting rooms, if all the rooms are occupied, then we schedule a new room. To check all the previous scheduled meetings, we keep a priority queue by finishing time of all the scheduled meetings. Assume there are d number of rooms, then checking takes logd time.
3. count the number of rooms.
The run time will be nlogn + nlogd = nlogn time.
class Meeting {
int startTime;
int endTime;
public Meeting(int s, int e) {
startTime = s;
endTime = e;
}
}
class solution {
public int minRoom(ArrayList meetings) {
Collections.sort(meetings, new Comparator () {
@Override
public int compare(Meeting m1, Meeting m2) {
if (m1.endTime > m2.endTime)
return 1;
if (m1.endTime < m2.endTime)
return -1;
return 0;
}
}
int max = 1;
}
}
Feasible problem:
Given a serial of jobs that contains a processTime and a deadLine, check if you can schedule them so that all the Jobs are finished before deadline.
1.Sort the jobs by deadline.
2. Schedule the job by the order of deadline, see if any job can not finish before deadline, if so, it is not possible, otherwise, the problem is feasible.
Minimum Lateness problem:
Assume we have a serial of jobs that contains a processTime and a deadLine, the lateness is the time between the finish time and the deadline of the job, if the job is finished before the deadline, then the lateness is 0. How do you schedule the job to minimize the total lateness?
1. Sort the jobs in deadline
2. step through all the elements in the order of the deadline, pick the earliest deadline and sums up the lateness if exist.
3. return the lateness
Third follow up question, what if each meeting has a priority, how can we schedule a set of meeting that has the largest priority sum given one meeting room?
1. Sort the meetings according to the finish time (like the first question)
2. Try schedule meeting starting from the first one greedily and record the total priority, mark those meetings that has been scheduled
3. Pass through all the meetings and schedule any meeting that has not been marked in previous schedules. record the max total priority
Read full article from Scheduling Problem (greedy algorithm) | Hello World
