2018.8.12 今日头条研发岗笔试题总结

#include <string>

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

struct Interval {

long long start;

long long end;

Interval() : start(0), end(0) {}

Interval(long long s, long long e) : start(s), end(e) {}

};

bool com(const Interval& a, const Interval& b)

{

if (a.start != b.start)

return a.start < b.start;

if (a.end != b.end)

return a.end < b.end;

return false;

}

void SplitString(const string& s, vector<string>& v, const string& c)

{

string::size_type pos1, pos2;

pos2 = s.find(c);

pos1 = 0;

while (string::npos != pos2)

{

v.push_back(s.substr(pos1, pos2 - pos1));

pos1 = pos2 + c.size();

pos2 = s.find(c, pos1);

}

if (pos1 != s.length())

v.push_back(s.substr(pos1));

}

int main()

{

int m;

cin >> m;

vector<Interval> intervals;

for (int i = 0; i < m; ++i)

{

string s;

cin >> s;

vector<string> v;

SplitString(s, v, ";");

int num = v.size();

for (int j = 0; j < num; ++j)

{

vector<string> v0;

SplitString(v[j], v0, ",");

Interval x;

x.start = stoi(v0[0]);

x.end = stoi(v0[1]);

intervals.push_back(x);

}

}

sort(intervals.begin(), intervals.end(), com);

long long len = intervals.size();

vector<Interval> res;

long long start(0);

long long end(0);

for (long long i = 0; i < len;)

{

start = intervals[i].start;

end = intervals[i].end;

long long j = i + 1;

for (; j < len; ++j)

{

if (end < intervals[j].start)

break;

end = max(end, intervals[j].end);

}

res.push_back(Interval(start, end));

i = j;

}

long long len2 = res.size();

for (long long i = 0; i < len2; ++i)

{

cout << res[i].start << ',' << res[i].end;

if (i != len2 - 1)

cout << ';';

}

}

#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

bool cmp(pair<int, int>& p1, pair<int, int>& p2)

{

return (p1.second<p2.second )||(p1.second==p2.second && p1.first>p2.first);

}

int main()

{

int N, M;

cin>>N>>M;

vector<pair<int, int> > time(N);

for(int i=0; i<N; ++i)

{

int s, t; cin>>s>>t;

if(s>=t)t+=M;

time[i] = make_pair(s,t);

}

sort(time.begin(), time.end(), cmp);

int finalRes=0;

for(int j=0; j<N;++j) //j代表从第j个开始看

{

int res =0;

int cur0 = time[j].first;

int cur =cur0;

for(int i=0; i<N; ++i)

{

if(i+j<N&& time[i].first >= cur)

{

cur = time[i].second;

if(cur<cur0+M)

++res;

else break;

}

if(i+j>=N && time[i].first+M >= cur)

{

cur = time[i].second+M;

if(cur<cur0+M)

++res;

else break;

}

}

if(res>finalRes)

finalRes = res;

}

cout<<finalRes<<endl;

return 0;

}