Coursera OA1

昨天刚刚做了 Coursera OA1, 不过今天才发现地里已经有这么多材料了。惭愧，两道题，依然是 Nondominatable Entity, Royal Name.Nondominatable En

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

典排序），名字相同的话根据后面的罗马数字 从大到小排序。

PS： 感觉Coursera在狂发OA，超多人拿到了这个。 我也是海投拿的。

第一题Entity: 是否先按x递减和y递增将vector<pair<int,int>> entities排序：

1. auto comp = [](const pair<int,int>& a, <span style="line-height: 1.5;">const pair<int,int>& b</span><span style="line-height: 1.5;">) {</span>

复制代码

然后就只用看y分量，只要是当前最大值的entity就是一个满足条件的元素（不能被其它entity dominate）：total time complexity O(N logN)

1. int undominated(<span style="line-height: 1.5; background-color: rgb(255, 255, 255);">vector<pair<int,int>>& entities</span><span style="line-height: 1.5;">) {</span>

复制代码

第一题Entity: 是否先按x递减和y递增将vector<pair<int,int>> entities排序：

1. 
   
2. auto comp = [](const pair<int,int>& a, const pair<int,int>& b) {
   
3.   return (a.first >b.first) || (a.first == b.first && a.second < b.second);
   
4. }
   

复制代码

然后就只用看y分量，只要是当前最大值的entity就是一个满足条件的元素（不能被其它entity dominate）：total time complexity O(N logN)

1. 
   
2. int undominated(vector<pair<int,int>>& entities) {
   
3.   sort(entities.begin(), entities.end(), comp);
   
4.   int max = INT_MIN, count = 0;
   
5.   for (int i = 0; i < entities.size(); i++) {
   
6.     if (entities.second >= max) { count++; max = entities.second; }
   
7.   }
   
8.   return count;
   
9. }
   

复制代码