Dynamic Programming | Set 20 (Maximum Length Chain of Pairs)
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest
chain which can be formed from a given set of pairs.
Source:Amazon Interview | Set 2
For example, if the given pairs are {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }, then the longest chain that can be formed is of length 3, and the chain is {{5, 24}, {27, 40}, {50, 90}}
This problem is a variation of standardLongest Increasing Subsequenceproblem. Following is a simple two step process.
1) Sort given pairs in increasing order of first (or smaller) element.
2) Now run a modified LIS process where we compare the second element of already finalized LIS with the first element of new LIS being constructed.
http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/
本博客贴出动态规划法解和贪心法的程序。
动态规划法的时间效率是O(n*n);
而贪心法的效率是O(nlgn),主要是因为sort需要O(nlgn)的时间效率,而贪心法本身只需要O(n).
// Structure for a pair
struct pairChain
{
int a;
int b;
};
// This function assumes that arr[] is sorted in increasing order
// according the first (or smaller) values in pairs.
int maxChainLengthDP( struct pairChain arr[], int n)
{
if (n < 2) return n;
int *A = new int[n];
A[0] = 1;
int max_len = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
A[i] = 1;
if (arr[i].a > arr[j].b) A[i] = A[i] < A[j]+1? A[j]+1:A[i];
max_len = max_len < A[i]? A[i]:max_len;
}
}
return max_len;
}
bool operator<(pairChain p1, pairChain p2)
{
return p1.b < p2.b;
}
#include<algorithm>
int maxChainLengthGreedy( struct pairChain arr[], int n)
{
if (n < 2) return n;
std::sort(arr, arr+n);
int max_len = 1;
int active_p = 0;
for (int i = 1; i < n; i++)
{
if (arr[i].a > arr[active_p].b)
{
max_len++;
active_p = i;
}
}
return max_len;
};
分享到:
相关推荐
geeks for geeks上的资源,大家下载下,我攒点几分,呵呵。
极客换极客 Geeks-For-Geeks 实习文章 使用 scapy 嗅探数据包 - 使用 Javascript 和 DOM 创建棋盘模式 - 如何将链接从一个 iframe 加载到另一个 iframe -
geeks-for-geeks-solutions:有关Geeks-for-Geeks的问题的解决方案。解决方案可用于C ++
Linux For Non-Geeks - A Hands-On, Project-Based, Take-It-Slow Guidebook 2004
样本AEM项目模板 这是基于AEM的应用程序的项目模板。 它旨在作为最佳实践示例集,也是开发您自己的功能的潜在起点。 模组 模板的主要部分是: 核心:包含所有核心功能(例如OSGi服务,侦听器或调度程序)以及与组件...
以团队形式建立网站(Git合作) 在开发典型网站时,练习您在GIT中的技能。 每个学生在网站的不同部分使用不同的文件工作,并且最高年级的学生可以担任团队负责人(用于集成和部署),除非老师更愿意成为整个班级的...
COMO INICIAR 克雷尔埃尔恩托尔诺 pipenv shell 安装依赖 pipenv install 克雷拉迁徙 pipenv run init pipenv run migrate pipenv run upgrade Ejecutar la API pipenv run start ... - Cambiar la variable @...
带有React JS的WebApp样板 要求: 确保您使用的是节点版本10 安装软件包: $ npm install 创建一个.env文件: $ cp .env.example .env 开始编码! 以及具有实时重新加载功能的webpack开发服务器(适用于Windows...
语言:English (United States) 1.提醒一下,每次访问特定的URL时,您应该打开另一个URL 1.just每次访问特定的URL时,您应该打开另一个 URL
语言:English 随时随地访问Chennai Geeks。 由ZathraC开发 除了Chennai Geeks网页之外,您还可以使用此扩展程序随时随地访问群发信息。
Ubuntu for Non-Geeks (Fourth Edition)
经典的Ubuntu Linux学习书籍,希望能给大家带来帮助,谢谢!
Geeks人工神经网络(GANN)是一个开源项目,最初的理念是成为一种新的更高级的ANN,该ANN可以作为其他应用程序的平台。 换句话说,GANN应该被视为“黑匣子”。
访问钦奈极客在旅途中。由ZathraC开发 除了钦奈极客网页,您可以通过此扩展程序访问群发邮件。 支持语言:English
关于网络游戏和极客的最新的链接。玩家的必须 简单而美丽。通过网络为您带来最新的游戏新闻,评论,视频和互动。... Geeks Fest将替换您的默认标签,它将成为您的主页,所以您不要不要错过任何东西。 支持语言:English
语言:English 游戏和怪物的最新鲜链接,来自网络。 游戏玩家必须 简单而美丽。 从网络上带来最新鲜的游戏新闻,评论,视频和交互式。 所有的游戏和极客都需要。 在那里享受最鼓舞人心的东西。 永远不要错过下一个...
Geeks3D Furmark(OpenGL显卡基准测试工具)V1.17.1 中文官方版
Hardware Hacking Projects for Geeks 英文chm 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
geek极客们都用什么神器,这篇文章给了你答案。
geeks-web.github.io