admin 管理员组文章数量: 887016
【荣耀2021编程题】薅羊毛
薅羊毛
- 题目描述
- 解题思路
题目描述
蓐羊毛活动：
药店为了吸引顾客，每天举行多场老年人养生讲座，内场主题不同，开始时间，时长都可能不同，参加者入场时签名，散场时能获得一个红包，参加下一场的条件，下一场开始的时间大于等于上一场结束时间。
王奶奶在家没事做，就像蓐羊毛，挣红包。针对几场讲座的通知，请你给王奶奶设计一个计划表，告诉她参加哪几场，让她挣的红包最多（只看红包个数）。
注意：如果有多种结果收益相同，最终结果挑选结束时间早的那场数据，如果结束时间一样，选开始晚的。
比如：
（3,6）（1,5）（6.7）
那么有两种安排
1、（3,6）（6,7）
2、（1,5）（6,7）
最终挑选结束早的那场（1,5），最终推荐给王奶奶的计划表为（1,5）（6,7）
比如：
（6,7）（8,10）（9,10）
那么有两种安排
1（6,7）（8,10）
2（6,7）（9,10）
最后一场，结束时间一样，选开始晚的那场（9,10），最终推荐给王奶奶的计划表为（6,7）（9,10）
输入描述
每一对括号表示一场数据，开始时间和结束时间以“，”隔开，场与场之间以空格分开，如下所示：
(3,6) (4,5) (6,7) (8,10) (9,10)
输出描述
第一行表示总共参加的场次，以关键字（count）加“：”输出
第二行表示具体参加的场次，场与场之间以空格分开，按结束时间升序排列
count:3
(4,5) (6,7) (9,10)
解题思路
这是一道典型的区间排序问题。我们需要按照题目描述中的要求对场次进行排序，然后依次检索出合适的场次。
- 按照会议的结束时间从小到大排序
- 如果结束时间一样，则按照开始时间从大到小排序
然后对排序后的链表执行贪心遍历。将链表的第一个元素加入到结果链表中，因为它一定是必须要参加的会议（相对的，开始时间晚，结束时间早），然后将它的结束时间作为标记，依次遍历链表。当遇到下一个元素的起始时间大于该标记，即说明下一场会议的开始时间晚于上一场的结束时间，说明这个会议可以参加。因为我们已经按照结束时间排序了，所以可以保证我们选择的会议一定是相对结束时间早的那一场。因此，将该会议加入到结果链表中。
最终返回结果链表。
代码如下：
package com.seckill.secondkill.utils;import java.util.*;class Letcure {public int begin;public int end;public Letcure(int begin, int end) {this.begin = begin;this.end = end;}
}public class Lectures {private static List<Letcure> letcureList = new ArrayList<>();private static List<Letcure> outputsList = new ArrayList<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNextLine()) {String[] copules = sc.nextLine().split(" ");int res = solution(copules);System.out.println("count:" + res);for (int i = 0; i < outputsList.size(); i++) {System.out.print("(" + outputsList.get(i).begin + "," + outputsList.get(i).end + ")" + " ");}System.out.println();}sc.close();}private static int solution(String[] copules) {if (copules.length <= 0) {return 0;}List<Letcure> inputList = new ArrayList<>();for (int i = 0; i < copules.length; i++) {String[] couple = copules[i].substring(1, copules[i].length() - 1).split(",");int begin = Integer.parseInt(couple[0]);int end = Integer.parseInt(couple[1]);Letcure letcure = new Letcure(begin, end);letcureList.add(letcure);}Collections.sort(letcureList, new Comparator<Letcure>() {@Overridepublic int compare(Letcure o1, Letcure o2) {// 如果结束时间一致，开始时间晚的排在前面；否则，结束时间早的排在前面return o1.end == o2.end ? o2.begin - o1.begin : o1.end - o2.end;}});int lastEnd = letcureList.get(0).end;outputsList.add(letcureList.get(0));for (int i = 1; i < letcureList.size(); i++) {if (letcureList.get(i).begin>=lastEnd){lastEnd = letcureList.get(i).end;outputsList.add(letcureList.get(i));}}return outputsList.size();}
}
执行结果
本文标签： 荣耀2021编程题薅羊毛
版权声明：本文标题：【荣耀2021编程题】薅羊毛 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732357613h1534889.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论