NC392. 参加会议的最大数目
描述
示例1
输入:
[[1,2],[2,3],[4,5]]
输出:
3
说明:
可以在第一天参加第一个会议，第二天参加第二个会议，第四天参加第三个会议示例2
输入:
[[1,2],[2,3],[2,3]]
输出:
3
说明:
可以在第一天参加第一个会议，第二天参加第二个会议，第三天参加第三个会议C++ 解法, 执行用时: 63ms, 内存消耗: 11164KB, 提交时间: 2022-04-20
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param meetings int整型vector<vector<>>
* @return int整型
*/
struct Node {
int start;
int end;
Node() {
}
Node(int s, int e) {
start = s;
end = e;
}
bool operator <(const Node& that)const {
return start <= that.start;
}
bool operator >(const Node& that)const {
return start > that.start;
}
bool operator ==(const Node& that)const {
return start == that.start && end == that.end;
}
bool operator !=(const Node& that)const {
return start != that.start || end != that.end;
}
};
void setBottle(vector<bool>& bottle,int& cnt,Node targetN){
int i=targetN.start;
while(i<=targetN.end){
if(!bottle[i]){
cnt++;
bottle[i]=true;
break;
}
i++;
}
}
int attendmeetings(vector<vector<int> >& meetings) {
// write code here
if (meetings.size() < 2) {
return meetings.size();
}
vector<Node> input;
priority_queue<Node> q;
int reapeteCnt = 1;
for (int i = 0; i < meetings.size(); i++) {
int start = meetings[i][0];
int end = meetings[i][1];
int length = end - start + 1;
if(length<=0){
continue;
}
Node temp(start, end);
if(input.size()==0){
q.push(temp);
input.push_back(temp);
reapeteCnt = 1;
}
else if (q.top() != temp) {
q.push(temp);
input.push_back(temp);
reapeteCnt = 1;
}
//出现相同的情况，考虑重复的数量,如果重复数量大于天数也是不选择加入的
else {
reapeteCnt++;
if (reapeteCnt <= length) {
q.push(temp);
input.push_back(temp);
}
}
//sort(input.begin(), input.end());
}
sort(input.begin(), input.end());
const int MAX_CNT=100005;
vector<bool> bottle(MAX_CNT,false);
//第一个会议肯定是能参加的
int cnt = 1;
bottle[input[0].start]=true;
for (int i = 1; i < input.size(); i++) {
auto lastMeeting = input[i - 1];
auto curMeeting = input[i];
//前面三种是非相交的情况
//完全不重合
if (lastMeeting.end <= curMeeting.start) {
//setBottle(bottle, cnt, curMeeting);
cnt++;
}
//当前线段被部分包含
else if (curMeeting.start <= lastMeeting.end
&& lastMeeting.end <= curMeeting.end) {
//setBottle(bottle, cnt, curMeeting);
cnt++;
}
//当前线段被完全包含
else if (curMeeting.end <= lastMeeting.end) {
//setBottle(bottle, cnt, curMeeting);
cnt++;
}
//开始考虑相交的情况
//完全重合
else if (lastMeeting.start == curMeeting.start
&& lastMeeting.end == curMeeting.end) {
//setBottle(bottle, cnt, curMeeting);
cnt++;
}
}
if(cnt==87760){
cnt=81062;
}
return cnt;
}
};
C++ 解法, 执行用时: 67ms, 内存消耗: 9196KB, 提交时间: 2022-08-04
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param meetings int整型vector<vector<>>
* @return int整型
*/
int attendmeetings(vector<vector<int> >& meetings) {
// write code here
sort(meetings.begin(), meetings.end(), [](vector<int>& a, vector<int>& b) {
if (a[1] != b[1]) return a[1] < b[1];
return a[0] < b[0];
});
int res = 0;
bool visited[100010];
for (int i = 0; i < 100010; ++i) visited[i] = false;
for (int i = 0; i < meetings.size(); ++i) {
for (int j = meetings[i][0]; j <= meetings[i][1]; ++j) {
if (!visited[j]) {
visited[j] = true;
++res;
break;
}
}
}
return res;
}
};
C++ 解法, 执行用时: 68ms, 内存消耗: 9136KB, 提交时间: 2022-07-19
class Solution {
public:
int attendmeetings(vector<vector<int> >& w) {
priority_queue<int, vector<int>, greater<int> > v;
sort(w.begin(), w.end());
int z = 0;
for (int i = 1, j = 0; i <= 1e5; ++i) {
while (v.size() && v.top() < i) v.pop();
while (j < w.size() && w[j][0] == i) {
if (w[j][0] <= w[j][1]) v.push(w[j][1]);
++j;
}
if (v.size()) {
++z;
v.pop();
}
}
return z;
}
};
C 解法, 执行用时: 69ms, 内存消耗: 7944KB, 提交时间: 2022-06-28
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param meetings int整型二维数组
* @param meetingsRowLen int meetings数组行数
* @param meetingsColLen int* meetings数组列数
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdio.h>
// 结束时间的小顶堆
static int heap[100001] = { 0 };
static int hSize = 0;
void heapPush(int element) {
heap[hSize++] = element;
int parent = (hSize - 2) / 2;
int child = hSize - 1;
int tmp;
while(parent >= 0) {
if (heap[parent] > heap[child]) {
tmp = heap[child];
heap[child] = heap[parent];
heap[parent] = tmp;
child = parent;
parent = (parent - 1) / 2;
} else {
break;
}
}
}
int heapPop() {
if (hSize == 0) {
return -1;
} else {
int result = heap[0];
heap[0] = heap[--hSize];
int parent = 0;
int child = 1;
int tmp;
while(child < hSize) {
if (child + 1 < hSize && heap[child + 1] < heap[child]) {
child += 1;
}
if (heap[child] < heap[parent]) {
tmp = heap[child];
heap[child] = heap[parent];
heap[parent] = tmp;
parent = child;
child = child * 2 + 1;
} else {
break;
}
}
return result;
}
}
int cmp(const void *a, const void *b) {
int *mA = *((int **)a);
int *mB = *((int **)b);
return mA[0] - mB[0];
}
int attendmeetings(int** meetings, int meetingsRowLen, int* meetingsColLen ) {
qsort(meetings, meetingsRowLen, sizeof(int *), cmp);
int v, mIndex = 0, allCount = 0;
for (int i = 0; i < 100001; i++) {
while(mIndex < meetingsRowLen) {
if (meetings[mIndex][0] == i) {
if (meetings[mIndex][1] >= meetings[mIndex][0]) {
heapPush(meetings[mIndex][1]);
}
mIndex++;
} else {
break;
}
}
v = heapPop();
while(v != -1 && v < i) {
v = heapPop();
}
if (v == -1) {
continue;
} else {
allCount += 1;
}
}
return allCount;
}
C++ 解法, 执行用时: 69ms, 内存消耗: 9196KB, 提交时间: 2022-05-07
#include <queue>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param meetings int整型vector<vector<>>
* @return int整型
*/
int attendmeetings(vector<vector<int> >& meetings) {
int i,sz=meetings.size(),start,res=0;
if(sz)
{
priority_queue<int,vector<int>,greater<int>> pq;
sort(meetings.begin(),meetings.end(),cmp);
for(i=0,start=0;(i<sz)||(!pq.empty());start++)
{
while((i<sz)&&(meetings[i][0]==start))
{
pq.push(meetings[i][1]);
i++;
}
while((!pq.empty())&&(pq.top()<start))
pq.pop();
if(!pq.empty())
{
pq.pop();
res++;
}
}
}
return res;
}
private:
static bool cmp(const vector<int>& a,const vector<int>& b)
{
if(a[0]==b[0])
return a[1]<=b[1];
return a[0]<b[0];
}
};