l*********i
发帖数: 28 | 1 面试官问design algorithm，去schedule课程表，学校有n个rooms，给你所有课程的
schedule，让我排出课表怎样不time conflict?
好像感觉是dynamic programming，又好像Integer Linear Programming 的优化问题，
请问怎么破？ |
e********2
发帖数: 495 | 2 什么公司？
【在 l*********i 的大作中提到】
: 面试官问design algorithm，去schedule课程表，学校有n个rooms，给你所有课程的
: schedule，让我排出课表怎样不time conflict?
: 好像感觉是dynamic programming，又好像Integer Linear Programming 的优化问题，
: 请问怎么破？
|
d******v
发帖数: 801 | |
l*********i
发帖数: 28 | 4 leetcode 里是课程 prerequisite 的题，这个是schedule到rooms with no blame.
【在 d******v 的大作中提到】
: 这题leetcode原题
|
h******6
发帖数: 2697 | |
j***y
发帖数: 1640 | 6 greedy algorithm.
先把课程排序。 最早结束的排前面。
PriorityQueue hold N LinkedList (# of classroom),最早空出的排前面。
先把前 N 课放进去。
loop:
popout a node , add new course to it, push it back, |
c*****m
发帖数: 271 | 7 如果是假设最优解不会导致conflict的话，可以用贪心吧？课程按开始结束时间排序，
然后把所有教室的（available starttime, id）放在priority queue里面。对于排好
序的每一个课程，分配给queue头的教室（有最小的starttime），将该教室的开始时间
更新为该课程的endtime。错了请拍！
如果不管怎样排都有conflict就不知道怎么搞了 |
c*******t
发帖数: 123 | 8 凡是在版上问leetcode原题的，都应该打屁屁。
【在 l*********i 的大作中提到】
: 面试官问design algorithm，去schedule课程表，学校有n个rooms，给你所有课程的
: schedule，让我排出课表怎样不time conflict?
: 好像感觉是dynamic programming，又好像Integer Linear Programming 的优化问题，
: 请问怎么破？
|
l*******e
发帖数: 127 | 9 跟LC 上的meeting schedule 2类似吧，那个求需要几个room.
面试官问design algorithm，去schedule课程表，学校有n个rooms，给你所有课程的
schedule，让我排出课表怎样不time conflict?好像感觉........
【在 l*********i 的大作中提到】
: 面试官问design algorithm，去schedule课程表，学校有n个rooms，给你所有课程的
: schedule，让我排出课表怎样不time conflict?
: 好像感觉是dynamic programming，又好像Integer Linear Programming 的优化问题，
: 请问怎么破？
|
y*********e
发帖数: 518 | 10 当怎么排都有conflict的时候就抛异常呗。代码如下：
struct class {
int class_id;
int start_time;
int end_time;
}
// sort by start_time
struct room {
int available_start_time;
vector class_ids;
}
// sort by available_start_time
vector find_scheduling(
vector rooms,
vector classes) {
priority_queue rq(rooms.begin(), rooms.end());
priority_queue cq(classes.begin(), classes.end());
while (!cq.empty()) {
const class& c = cq.dequeue();
for (room& r : rq) {
if (r.available_start_time >= c.start_time) {
rq.dequee(r);
r.available_start_time = c.end_time;
r.class_ids.push_back(c.class_id);
rq.enqueue(r);
continue;
}
}
throw ‘no room available’;
}
return vector(rq.begin(), rq.end());
}
我们把输入的rooms和classes都按照start_time排序好了。
通过greedy解出来的一定就是最优解。
【在 c*****m 的大作中提到】
: 如果是假设最优解不会导致conflict的话，可以用贪心吧？课程按开始结束时间排序，
: 然后把所有教室的（available starttime, id）放在priority queue里面。对于排好
: 序的每一个课程，分配给queue头的教室（有最小的starttime），将该教室的开始时间
: 更新为该课程的endtime。错了请拍！
: 如果不管怎样排都有conflict就不知道怎么搞了
|
