张三大学学的是机械专业，毕业后他用有限的资金开了一家摩托车零件加工厂，专门为摩托车制造商制造零件。由于资金有限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家摩托车制造商需要他加工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开始和结束时间相同不算冲突）。

张三希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件的加工时间要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得尽量多的加工费，张三不知如何进行取舍。

现在请你帮张三设计一个程序，合理选择部分（或全部）零件进行加工，使得得到最大的加工费。
【输入】
每组测试数据的第一行是一个整数n(n<=30000)，表示共有n个零件须加工。
接下来的n行中，每行有3个整数，分别表示每个零件加工的时间要求。
第一个表示开始时间，第二个表示该零件加工的结束时间，第三个表示加工该零件可以得到的加工费。
注：数据中的每个数值不会超过100000.
【输出 】
对每组测试数据,输出一个整数，表示张三可以得到的最大加工费。
【输入样例 】
3
1 3 10
4 6 20
2 5 25
【输出样例 】
30

重发的作业？

哦，楼主还是有诚意的，这次加了20分。只是楼主似乎不善言词，除了问题没有多说一个字，这可不好。

语言表达能力是一种很重要的素质，甚至超过你其它所有能力。抓紧时间锻炼一下吧。

不管楼主的问题是不是作业，现在论坛内能解决这个问题的人估计不超过三个（算我在内）。

呵呵，这话有没有激怒大家？要不，我再发个悬赏令？

没人响应？

从这贴的时间算起，第一个正确高效解决这个问题的人，将可获得我的赠分。规则如下

2小时内完成，送500专家分。

24小时内完成，送100专家分。

48小时内完成，送50专家分。

再次重申：赠分只给第一个人，赠予的分数将由这第一个人提交代码的时间决定。

时间以提交代码的贴子时间为准，贴子跟在这里就可以。也可以单独发贴，但请用站内短消息提醒我查看，否则我可能会漏掉。

关于正确性，我很想找到这题实际的OJ，但搜索无果，如果哪位能提供将十分感谢。否则，我将自己准备若干数据用于测试。

关于高效，这里给出一个明确的定义：如果有人能提供OJ，则以AC为准，否则，将以我的数据为准，能在1秒内给出正确结果视为高效。（ps:我一定会准备几组n=30000的数据）

现在开始计时！

我来说说我思路吧，将一组数据（开始时间，结束时间，工钱）作为一个节点，根据时间的冲突这一条件将所有的节点构造成一颗树或森林，然后求出每一路径的权值总和，最后比较出最优的结果。

只是个大体思路，抛砖引玉~

不妨将你的想法实现成代码如何？

致各位：

距离头奖结束的时间已经过半，难道要轮空？

这样吧，我再设10个参与奖，只要能正确计算N<=20的数据（效率不作要求），奖励10分。

奖励有效期：以我上一贴时间开始，48小时内前10名提交满足要求代码的均可获奖。

欢迎大家积极参与！

额，对于算法这玩意我有点敬畏，我还是旁观吧

无妨。多接触就不会畏了。

编程就是在写算法，Hello World 亦是算法。（你不能因为y=1简单就不承认它是函数吧）

哈哈，话是这么说，但是此算法非彼算法啊。。。。嗯，我好好想想该怎么去实现

呵呵，再次大放送，48小时内，只要有代码（意图贴近此题的），无论对错、代码完整与否，皆奖励5分。

每人只奖励1次，名额不限。这次叫鼓励奖吧。

[ 本帖最后由 beyondyf 于 2013-6-2 22:14 编辑 ]