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
From:
https://hellosmallworld123.wordpress.com/2014/05/30/arranging-the-meeting-room/
相关推荐
Flexible job-shop scheduling problem by genetic algorithm
problem under elecyticity price uncertainty. This model comprehensively considers electricity price fluctuations, unit parameters and load re- quirement, and it can be adjusted by adjusting the size ...
云计算中融入贪心策略的调度算法研究,周舟,胡志刚,鉴于Min-Min算法优先调度小任务而Max-Min算法优先调度大任务而导致云系统资源不平衡的问题,提出了一种新的算法叫Min-Max. Min-Max算法对时
A non-preemptive scheduling algorithm for softA non-preemptive scheduling algorithm for soft
该文件是经典的EV调度问题,采用滑窗变速优化方法对大电网中的Ev进行实时调度。考虑网损/电池老化/充电成本等,用全局优化和局部优化对比。(包含源码)
基于遗传算法的一类无序加工调度 A Class of Job- shop Scheduling with Genetic Algorithm.pdf
Based on the former research, we proposed an efficient DVS scheduling algorithm named CC-R-E-DVS, which is a kind of EDF scheduling. The DVS we proposed can reasonably use the slack time and reduce ...
cross-layer scheduling algorithm in WIRELESS
Parallel-Machine-Scheduling-with-Deep-Q-network-AlgorithmCode env_batch.py - ?憓?code | State Reward Action *這個檔案沒有要修改的參數,主要把State的生成、指派工作(job)以及計算reward在這個檔案運作...
包括了简单的数据库设计,其中数据库包括了教师,学生以及课程的状态,具有一定参考价值
Laravel开发-scheduling 其他Laravel包的独立调度。
An EDF-based Restricted-Migration Scheduling Algorithm for Multiprocessor Soft Real-Time Systems.pdf
Real-Time Systems - Scheduling, Analysis And Verification. Classic textbook for computer science students.
CPU-Scheduling实验报告PDF文件
Angular-medical-appointment-scheduling.zip,中小型医疗机构预约排程系统概念展示,Angularjs于2016年发布,是Angularjs的重写版。它专注于良好的移动开发、模块化和改进的依赖注入。angular的设计目的是全面解决...
Flexible job-shop scheduling problem (FJSP) is an extended traditional job-shop scheduling problem, which more approximates to practical scheduling problems. This paper presents a multi-objective ...
Priority-scheduling Task2实验报告.docx
Priority-scheduling Task1实验报告.docx
资源来自pypi官网。 资源全名:chaosplatform-scheduling-0.1.0.tar.gz
a program that implements the following disk-scheduling algorithms: FCFS, SSTF, SCAN, C-SCAN, Look and C-Look