【荣耀2021编程题】薅羊毛

缺乏、安全感 2022-08-28 08:45 274阅读 0赞

### 薅羊毛 ###

*  题目描述
 *  解题思路

# 题目描述 #

**蓐羊毛活动：**  
药店为了吸引顾客，每天举行多场老年人养生讲座，内场主题不同，开始时间，时长都可能不同，**参加者入场时签名，散场时能获得一个红包**，参加下一场的条件，下一场开始的时间大于等于上一场结束时间。

王奶奶在家没事做，就像蓐羊毛，挣红包。针对几场讲座的通知，请你给王奶奶**设计一个计划表**，告诉她参加哪几场，让她挣的**红包最多**（只看红包个数）。

注意：**如果有多种结果收益相同，最终结果挑选结束时间早的那场数据，如果结束时间一样，选开始晚的。**  
比如：  
（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)

# 解题思路 #

这是一道典型的区间排序问题。我们需要按照题目描述中的要求对场次进行排序，然后依次检索出合适的场次。

1.  按照会议的结束时间从小到大排序
2.  如果结束时间一样，则按照开始时间从大到小排序

然后对排序后的链表执行贪心遍历。将链表的第一个元素加入到结果链表中，因为它一定是必须要参加的会议（相对的，开始时间晚，结束时间早），然后将它的结束时间作为标记，依次遍历链表。当遇到下一个元素的起始时间大于该标记，即说明下一场会议的开始时间晚于上一场的结束时间，说明这个会议可以参加。因为我们已经按照结束时间排序了，所以可以保证我们选择的会议一定是相对结束时间早的那一场。因此，将该会议加入到结果链表中。

最终返回结果链表。  
**代码如下：**

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>() {
        
                @Override
                public 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();
        }
    }

**执行结果**  
![执行结果][84d758f047b84b8ba7b73c2214471d12.png]

[84d758f047b84b8ba7b73c2214471d12.png]: /images/20220828/842dace86f5d4d49b2983a475b6440ab.png