阿里编程测验，好难

#include <iostream>

#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <cassert>
#include <map>
#include <algorithm>

using namespace std;

class Interval
{
public:
explicit Interval(size_t left, size_t right)
: mLeft(left),
mRight(right)
{
assert(left <= right);
}

size_t left() const
{
return mLeft;
}

size_t right() const
{
return mRight;
}

private:
size_t mLeft;
size_t mRight;
};

inline bool operator<(const Interval& a, const Interval& b)
{
return a.right() < b.left();
}

class TwoInterval
{
public:
explicit TwoInterval(const Interval& left, const Interval& right)
: mLeft(left),
mRight(right)
{
assert(left < right);
}

const Interval& left() const
{
return mLeft;
}

const Interval& right() const
{
return mRight;
}

private:
Interval mLeft;
Interval mRight;
};

inline bool within(const TwoInterval& a, const TwoInterval& b)
{
return b.left() < a.left() && a.right() < b.right();
}

void input(vector<TwoInterval>& twos)
{
int m = 0;
{
string s;
getline(cin, s);
istringstream is(s);
is >> m;
}
for(int i = 0; i < m; ++i) {
string s;
getline(cin, s);
istringstream is(s);
size_t a, b, c, d;
is >> a >> b >> c >> d;
Interval left(a, b);
Interval right(c, d);
twos.emplace_back(left, right);
}
}

// ====== 填入你自己的逻辑 ========

int intussusception(vector<TwoInterval>&)
{
}

// ====== 结束 ========

int main() {
vector<TwoInterval> twos;
input(twos);

cout << intussusception(twos) << endl;

return 0;
}

#阿里巴巴#

全部评论

推荐最新楼层

SEU-YER

楼主

东南大学 C++

// ====== 填入你自己的逻辑 ======== /////********************************///// /* 看了大家的回复，才知道自己漏看了题目，后来想了想，现将思路贴出来，供大家交流具体见我的博客：http://blog.csdn.net/bxw1992/article/details/74534157 目的：最多可以取出多少个能够组成嵌套集思路：如果存在一个子嵌套集，而新增加的一个二段模式与子嵌套集的某个二段模式冲突（不相互嵌套），它虽然不能加入该嵌套子集，但是它却可以和该子集中不冲突的其他二段模式组成子集，所以很难处理。因此，从这个角度来思考，太过于复杂。从上面的思路中我们可以得到一些有用的结论：针对存在的一个子嵌套集，新的二段模式的加入，可以生成新的子嵌套集，也就是造成分支；进一步我们可以认为，一个二段模式最多可以生成一个分支，而且一个分支主要是因为某个二段模式与其他嵌套集冲突造成的，也就是一个二段模式可以对应一个嵌套集；N个二段模式最多组成N个独立的嵌套集。算法流程： 1、初始N个嵌套集，分别包含编号0~N-1二段模式 2、针对某个二段模式，遍历查看是否可以满足加入嵌套集的条件（两两相互嵌套，而且该二段模式之前不存在）满足的话，将其加入 3、找出最大的嵌套集 */ /////********************************///// inline bool operator==(const Interval& a, const Interval& b) { return (a.right() == b.right()) && (a.left() == b.left()); } inline bool operator==(const TwoInterval& a, const TwoInterval& b) { return (a.right() == b.right()) && (a.left() == b.left()); } bool confl(const TwoInterval& a, const TwoInterval& b) { if (!(within(a, b) || within(b, a))) return true; if (a == b) return true; return false; } bool add(vector<TwoInterval> &a, TwoInterval b) { for (TwoInterval ti : a) { if (confl(ti,b)) { return false; } } a.push_back(b); return true; } int intussusception(vector<TwoInterval>& two2) { int len = two2.size(); if (len < 2) return len; int max = 0; vector<vector<TwoInterval> > res(len); for (int i = 0; i < len; i++) { res[i].push_back(two2[i]); } for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { add(res[j], two2[i]); } } for (int i = 0; i < len; i++) { if (res[i].size()>max) { max = res[i].size(); } } return max; } // ====== 结束 ========

点赞回复分享

发布于 2017-07-06 13:04

牛客5207154号

百度_算法工程师

题目好像不完整啊，能否提供下完整的题目

点赞回复分享

发布于 2017-07-06 09:14

zhbei

中国科学院大学 C++

其实大多数人被这道题目的概念唬住了；二段式：其实就是区间呗嵌套集合：就是里面的所有区间两两之间都存在包含关系。题目要求：求能够包含最多区间数目的嵌套结合！

阿里编程测验，好难

全站热榜