区间调度问题详解

Posted on | In | Comments:

区间调度问题详解

这里是一个区间调度问题的总结学习，主要参考区间调度问题详解，思路方面原文已经非常清晰，这里就不在赘述，请直接参考原文。

最多区间调度

Greedy

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
const int MAX_N=100000;
//输入
int N,S[MAX_N],T[MAX_N];

//用于对工作排序的pair数组
pair<int,int> itv[MAX_N];

void solve()
{
    //对pair进行的是字典序比较，为了让结束时间早的工作排在前面，把T存入first，//把S存入second
    for(int i=0;i<N;i++)
    {
	    itv[i].first=T[i];
	    itv[i].second=S[i];
    }

    sort(itv,itv+N);

    //t是最后所选工作的结束时间
    int ans=0,t=0;
    for(int i=0;i<N;i++)
    {
	    if(t<itv[i].second)//判断区间是否重叠
	    {
		    ans++;
		    t=itv[i].first;
	    }
    }

    printf(“%d\n”,ans);
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve()
{
	//1. 对所有的区间进行排序
	sort_all_intervals();

	//2. 按照动态规划求最优解
	dp[0]=1;
	for (int i = 1; i < intervals.size(); i++) 
       {
		//1. 选择第i个区间
		k=find_nonoverlap_pos();
		if(k>=0) dp[i]=dp[k]+1;
		//2. 不选择第i个区间
		dp[i]=max{dp[i],dp[j]};
	}
}

最大区间调度

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
public int getMaxWorkingTime(List<Interval> intervals) {
		if(intervals==null || intervals.size()==0) return 0;
		Collections.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval i1, Interval i2) {
				return i1.getEndHour() != i2.getEndHour() ? i1.getEndHour() - i2.getEndHour() : i1.getEndMinute() - i2.getEndMinute();
			}
		});
		int[] maxTimes = new int[intervals.size()];
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<intervals.size(); i++) {
			Interval interval = intervals.get(i);
			int passMax = i>0 ? maxTimes[i-1] : 0;
			int takeMax = interval.getIntervalMinute();
			int lastIndex = binarySearchLastNorConflict(intervals, i-1, interval.getBeginMinuteUnit());
			takeMax += (lastIndex>=0 ? maxTimes[lastIndex] : 0);
			maxTimes[i] = Math.max(passMax, takeMax);
			if(maxTimes[i]>max) max = maxTimes[i];
		}
		return max;
	}
	
	public int binarySearchLastNorConflict(List<Interval> intervals, int right, int time) {
		int left = 0;
		while(left<=right) {
			int mid = (left + right) / 2;
			if(intervals.get(mid).getEndMinuteUnit()<=time) left = mid + 1;
			else right = mid - 1;
		}
		return right;
	}

带权的区间调度

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
const int MAX_N=100000;
//输入
int N,S[MAX_N],T[MAX_N];

//用于对工作排序的pair数组
pair<int,int> itv[MAX_N];

void solve()
{
    //对pair进行的是字典序比较，为了让结束时间早的工作排在前面，把T存入first，//把S存入second
    for(int i=0;i<N;i++)
    {
	    itv[i].first=T[i];
	    itv[i].second=S[i];
    }

    sort(itv,itv+N);

    dp[0] = (itv[0].first-itv[0].second)*V[0];
    for (int i = 1; i < N; i++)
    {
	    int max;

	    //select the ith interval
	    int nonOverlap = lower_bound(itv, itv[i].second)-1;
	    if (nonOverlap >= 0)
		    max = dp[nonOverlap] + (itv[i].first-itv[i].second)*V[i];
	    else
		    max = (itv[i].first-itv[i].second)*V[i];

	    //do not select the ith interval
	    dp[i] = max>dp[i-1]?max:dp[i-1];
    }
    printf(“%d\n”,dp[N-1]);
}

最小区间覆盖

将剩余的区间和新的左端点比较并选择右端点最大的区间，修改左端点，这时左端点就会变为end4，I4添加到最小覆盖区间中。依次处理剩余的区间，我们就获得了最优解

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
const int MAX_N=100000;
//输入
int N,S[MAX_N],T[MAX_N];

//用于对工作排序的pair数组
pair<int,int> itv[MAX_N];

int solve(int s,int t)
{
    for(int i=0;i<N;i++)
    {
	    itv[i].first=S[i];
	    itv[i].second=T[i];
    }

    //按照开始时间排序
    sort(itv,itv+N);

    int ans=0,max_right=0;
    for (int i = 0; i < N; )
    {
	    //从开始时间在s左侧的区间中挑出最大的结束时间
	    while(itv[i].first<=s)
	    {
		    if(max_right<itv[i].end) max_right=itv[i].end;
		    i++;
	    }	

	    if(max_right>s) 
        {
             s=max_right;
             ans++;
            if(s>=t) return ans;
        }
	    else //如果分界线左侧的区间不能覆盖s，则不可能有区间组合覆盖给定范围
	    {
                return -1;
	    }
    }
}

最大区间重叠（最少工人调度）

这里实际的代码是leetcode的minimal meeting room问题，但本质上就是最大区间重叠问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        // 用堆来管理房间的结束时间
        PriorityQueue<Integer> endTimes = new PriorityQueue<Integer>();
        endTimes.offer(intervals[0].end);
        for(int i = 1; i < intervals.length; i++){
            // 如果当前时间段的开始时间大于最早结束的时间，则可以更新这个最早的结束时间为当前时间段的结束时间，如果小于的话，就加入一个新的结束时间，表示新的房间
            if(intervals[i].start >= endTimes.peek()){
                endTimes.poll();
            }
            endTimes.offer(intervals[i].end);
        }
        // 有多少结束时间就有多少房间
        return endTimes.size();
    }
}