每日OJ题_牛客_NC383主持人调度(一)_排序_C++_Java
目录
牛客_NC383主持人调度(一)_排序
题目解析
C++代码
Java代码
牛客_NC383主持人调度(一)_排序
主持人调度(一)_牛客题霸_牛客网 (nowcoder.com)
描述:
有 n 个活动即将举办,每个活动都有开始时间与活动的结束时间,第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动,换句话说,一个主持人参与了第 i 个活动,那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。请问一个只有一个主持人能否举办全部活动。
题目解析
-
区间问题技巧:左端点排序或者按照右端点排序。
-
左端点排序后,仅需考虑后续区间是否能与前一个区间重叠即可。
C++代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param schedule int整型vector<vector<>>
* @return bool布尔型
*/
bool hostschedule(vector<vector<int> >& schedule) {
sort(schedule.begin(), schedule.end());
int sz = schedule.size();
for(int i = 1; i < sz; ++i)
{
if(schedule[i][0] < schedule[i - 1][1])
return false;
}
return true;
}
};
Java代码
import java.util.*;
public class Solution
{
public boolean hostschedule (ArrayList<ArrayList<Integer>> sc)
{
int m = sc.size(), n = sc.get(0).size();
int[][] schedule = new int[m][n];
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
schedule[i][j] = sc.get(i).get(j);
}
}
Arrays.sort(schedule, (v1, v2) -> {
return v1[0] - v2[0];
});
for(int i = 1; i < schedule.length; i++)
{
if(schedule[i][0] < schedule[i - 1][1])
return false;
}
return true;
}
}