C++会议调度器

假设我们有两个人的可用时间段列表slots1和slots2，以及会议时长d，我们需要找到对他们两个都适用且时长为d的最早时间段。如果没有满足要求的公共时间段，则显示空数组。这里时间段的格式是由两个元素[开始时间, 结束时间]组成的数组，表示从开始时间到结束时间的包含范围。我们可以假设同一个人的任何两个可用时间段不会相互重叠。也就是说，对于同一个人的任何两个时间段[s1, e1]和[s2, e2]，要么s1 > e2，要么s2 > e1。例如，如果输入为s1 = [[10,50], [60,120], [140,210]]，s2 = [[0,15], [60,70]]，时长 = 8，则输出为[60,68]。

为了解决这个问题，我们将遵循以下步骤：

• i := 0，j := 0，创建一个数组ans，对s1和s2进行排序。
• 当i < s1的大小 且 j < s2的大小时
  • end := s1[i, 1] 和 s2[j, 1]中的最小值
  • start := s1[i, 0] 和 s2[j, 0]中的最小值
  • 如果 end – start >= duration，则
    • 将start和(start + duration)插入ans数组，并返回ans。
  • 否则，如果s1[i, 1] < s2[j, 1]，则将i加1
  • 否则将j加1
• 返回ans

让我们看看下面的实现来更好地理解：

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
using namespace std;
bool cmp(vector <int> a, vector <int> b){
   return a[0]<b[0];
}
class Solution {
   public:
   vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
      int i =0;
      int j = 0;
      vector <int> ans;
      sort(slots1.begin(),slots1.end(),cmp);
      sort(slots2.begin(),slots2.end(),cmp);
      while(i<slots1.size() && j<slots2.size()){
         int end = min(slots1[i][1],slots2[j][1]);
         int start = max(slots1[i][0],slots2[j][0]);
         if(end-start>=duration){
            ans.push_back(start);
            ans.push_back(start+duration);
            return ans;
         } else if(slots1[i][1]<slots2[j][1]) {
            i++;
         } else {
         j++;}
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{10,50},{60,120},{140,210}};
   vector<vector<int>> v1 = {{0,15},{60,70}};
   Solution ob;
   print_vector(ob.minAvailableDuration(v, v1, 8));
}

输入

[[10,50],[60,120],[140,210]]
[[0,15],[60,70]]
8

输出

[60, 68, ]

Arnab Chakraborty

更新于：2020年4月30日

901 次查看

启动你的职业生涯

完成课程获得认证

开始