题目描述：

智能手机方便了我们生活的同时，也侵占了我们不少的时间。“手机App防沉迷系统”能够让我们每天合理的规划手机App使用时间，在正确的时间做正确的事。

它的大概原理是这样的：

1. 在一天24小时内，可注册每个App的允许使用时段；

2. 一个时段只能使用一个App，举例说明：不能同时在09:00-10:00注册App2和App3；

3. App有优先级，数值越高，优先级越高。注册使用时段时，如果高优先级的App时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段；如果App的优先级相同，则后添加的App不能注册。

举例1：

（1）注册App3前：
（2）App3注册时段和App2有冲突：
（3）App3优先级高，系统接受App3的注册，自动注销App2的注册：

举例2：

（1）注册App4：
（2）App4和App2及App3都有冲突，优先级比App2高，但比App3低，这种场景下App4注册不上

4. 一个App可以在一天内注册多个时段。

请编程实现，根据输入数据注册App，并根据输入的时间点，返回该时间点可用的App名称，如果该时间点没有注册任何App，请返回"NA"。

输入描述：

输入分3部分：第一行表示注册的App数N（N≤100）；第二部分包括N行，每行表示一条App注册数据；最后一行输入一个时间点，程序即返回该时间点的可用App。

2
App1 1 09:00 10:00
App2 2 11:00 11:30
09:30

数据说明如下：

1、N行注册数据以空格分隔，四项数据依次表示：App名称、优先级、起始时间、结束时间

2、优先级1-5，数字值越大，优先级越高

4、起始时间需小于结束时间，否则注册不上

5、注册信息中的时间段包含起始时间点，不包含结束时间点

输出描述：

输出一个字符串，表示App名称，或NA表示空闲时间。

补充说明：

1、用例保证时间都介于00:00-24:00之间；

2、用例保证数据格式都是正确的，不用考虑数据输入行数不够、注册信息不完整、字符串非法、优先级超限、时间格式不正确的问题。

示例

示例1

输入：

1
App1 1 09:00 10:00
09:30

输出：

App1

说明：

App1注册在9点到10点间，9点半可用的应用名是App1

示例2

输入：

2
App1 1 09:00 10:00
App2 2 09:10 09:30
09:20

输出：

App2

说明：

App1和App2的时段有冲突，App2的优先级比App1高，注册App2后，系统将App1的注册信息自动注销后，09:20时刻可用应用名是App2.

示例3

输入：

2
App1 1 09:00 10:00
App2 2 09:10 09:30
09:50

输出：

NA

说明：

App1被注销后，09:50时刻没有应用注册，因此输出NA。

题解思路

本题数量级较小，可以考虑暴力破解。

本题每注册一个App_registering前，都要去和已注册的所有App_registered进行比较：

注册时段是否有冲突？

如果没有冲突，则继续和下一个App_registered比较

如果有冲突，

则比较优先级 App_registering 的优先级高于（>）App_registered，则App_registered需要被注销，此时不能直接进行注销动作，因为我们需要确保 App_registering 可以注册后，才能进行注销。

App_registering 的优先级不高于（≤）App_registered，则App_registering不能注册，即终止后续比较

本题比较两个App注册时段冲突的方式，可以将App的注册时段的时间点信息，转化为分钟数数值，比如：

10:29

可以转化为：

10 * 60 + 29 = 629

这样两个App的时段比较，其实判断两个区间是否有交集,如果两个区间不相交，那么最大的开始端一定大于最小的结束端

	/**
	 * 如果两个区间不相交，那么最大的开始端一定大于最小的结束端
	 * @param app1
	 * @param app
	 * @return 时间段是否有交集
	 */
	public boolean hasInser(App app1, App app) {
		Boolean noInser = Math.max(app.startTime, app1.startTime) >= Math.min(app.endTime,  app1.endTime)
		return !noInser;
	}

源码 Java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.LinkedList;
import java.util.List;

public class AppChilden {

	Input input ;

	@BeforeEach
	public void init() {
		input = new Input("2\n" +
				"App1 1 09:00 10:00\n" +
				"App2 2 09:10 09:30\n" +
				"09:20");
		input = new Input("2\n" +
				"App1 1 09:00 10:00\n" +
				"App2 2 09:10 09:30\n" +
				"09:50");
	}

	@Test
	public void test() {
		List<App> list = new LinkedList<>();

		int registerCount = Integer.parseInt(input.nextLine());
		for (int i = 0; i < registerCount; i++) {
			if (list.isEmpty()) {
				list.add(new App(input.nextLine()));
			} else {
				App app = new App(input.nextLine());
				if (addable(list, app)){
					List<App> apps = new LinkedList<>();
					apps.add(app);
					for (App app1 : list) {
						if (!hasInser(app1, app)){
							apps.add(app1);
						}
					}
					list = apps;
				}
			}
		}

		String[] time = input.nextLine().split(":");
		int timeInt = Integer.valueOf(time[0]) * 60 + Integer.valueOf(time[1]);
		String appName = "NA";
		for (App app : list) {
			if (app.startTime <= timeInt && app.endTime > timeInt) {
				appName = app.appName;
			}
		}
		System.out.println(appName);
	}

	/**
	 * 思路就是如果两个区间不相交，那么最大的开始端一定大于最小的结束端
	 * @param app1
	 * @param app
	 * @return 时间段是否有交集
	 */
	public boolean hasInser(App app1, App app) {
		Boolean noInser = Math.max(app.startTime, app1.startTime) >= Math.min(app.endTime,  app1.endTime)
		return !noInser;
	}
	public boolean addable(List<App> list, App app) {
		boolean able = true;
		for (App app1 : list) {
			if (hasInser(app1, app)) {
				if (app.priority <= app1.priority) {
					return false;
				}
			}
		}
		return able;
	}

	class App{
		public String appName ;
		public int priority;
		public int startTime;
		public int endTime;
		
		public App(String info) {
			String[] split = info.split(" ");
			this.appName = split[0];
			this.priority = Integer.parseInt(split[1]);
			String[] start = split[2].split(":");
			this.startTime = Integer.parseInt(start[0]) * 60 + Integer.parseInt(start[1]) ;
			String[] end = split[3].split(":");
			this.endTime = Integer.parseInt(end[0]) * 60 + Integer.parseInt(end[1]) ;
		}
	}
}