牛牛找工作（题目来自牛客网）

题目

输入测试样例有两个正整数，分别表示工作的数量N（1e6）和小伙伴的数量M（1e6）。

思路解读

目标是每个小伙伴挑选低于或等于自己能力且报酬最高的工作，故按照能力从小到大进行排序，若能力相等，则按照报酬从大到小排序，这是第一轮排序，第二轮为筛选，因为能力一样的时候，报酬从大排到小，故挑选每个组的组长即可，即留下每个能力相等的工作的第一份工作；再一个是，能力从小排到大，若能力越大，报酬反而更少，则可以直接剔除，这样即可减少最后阶段每个小伙伴遍历寻找合适自己的工作的时间，这个时候我们如果一个一个去遍历的话，时间复杂度是O(n2)，1e6*1e6 = 1e12 > 1e9 ,大概率会报超时。

如愿报了超时

这个时候采用了有序表，有序表的各个操作时间复杂度均为O(logN)，循环n次后，时间复杂度为O(nlogn) < O(n2),如愿通过了

接下来简单说明一下有序表，java中有序表是红黑树，但是原理太过于复杂，我们暂时只需要知道如何去使用有序表就行，有序表可以被红黑树，avl树，跳表，size-balance-tree（SB树）实现，不同的实现之间，在使用层次和性能上看没区别，只有常数时间的区别

所有接口的性能为O（logN）

有序表和哈希表的区别：

哈希表有的功能，有序表一定有，哈希表的key（散乱组织，哈希函数）

有序表所有key有序组织

TreeMap构造函数

TreeMap有五种类型的构造函数：

1. **TreeMap（）：**使用其键的自然顺序创建一个新的空树图。
2. **TreeMap（比较器c）：**创建一个新的空树图，根据给定的比较器排序。
3. **TreeMap（地图）：**创建一个新的树图，其中包含与给定地图相同的映射，根据其键的自然顺序排序。
4. **TreeMap（SortedMap map）：**创建一个新的树图，其中包含相同的映射并使用与指定的有序映射相同的顺序。

TreeMap的API

Map.Entry<K,V>    ceilingEntry(K key)   
         返回一个键-值映射关系，它与大于等于给定键的最小键关联；如果不存在这样的键，则返回 null。  
K   ceilingKey(K key)   
         返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。  
void    clear()   
         从此映射中移除所有映射关系。  
Object  clone()   
         返回此 TreeMap 实例的浅表副本。  
Comparator<? super K> comparator()   
         返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。  
boolean containsKey(Object key)   
         如果此映射包含指定键的映射关系，则返回 true。  
boolean containsValue(Object value)   
         如果此映射为指定值映射一个或多个键，则返回 true。  
NavigableSet<K>   descendingKeySet()   
         返回此映射中所包含键的逆序 NavigableSet 视图。  
NavigableMap<K,V> descendingMap()   
         返回此映射中所包含映射关系的逆序视图。  
Set<Map.Entry<K,V>> entrySet()   
         返回此映射中包含的映射关系的 Set 视图。  
Map.Entry<K,V>    firstEntry()   
         返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。  
K   firstKey()   
         返回此映射中当前第一个（最低）键。  
Map.Entry<K,V>    floorEntry(K key)   
         返回一个键-值映射关系，它与小于等于给定键的最大键关联；如果不存在这样的键，则返回 null。  
K   floorKey(K key)   
         返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。  
V   get(Object key)   
         返回指定键所映射的值，如果对于该键而言，此映射不包含任何映射关系，则返回 null。  
SortedMap<K,V>    headMap(K toKey)   
         返回此映射的部分视图，其键值严格小于 toKey。  
NavigableMap<K,V> headMap(K toKey, boolean inclusive)   
         返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。  
Map.Entry<K,V>    higherEntry(K key)   
         返回一个键-值映射关系，它与严格大于给定键的最小键关联；如果不存在这样的键，则返回 null。  
K   higherKey(K key)   
         返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。  
Set<K>    keySet()   
         返回此映射包含的键的 Set 视图。  
Map.Entry<K,V>    lastEntry()   
         返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。  
K   lastKey()   
         返回映射中当前最后一个（最高）键。  
Map.Entry<K,V>    lowerEntry(K key)   
         返回一个键-值映射关系，它与严格小于给定键的最大键关联；如果不存在这样的键，则返回 null。  
K   lowerKey(K key)   
         返回严格小于给定键的最大键；如果不存在这样的键，则返回 null。  
NavigableSet<K>   navigableKeySet()   
         返回此映射中所包含键的 NavigableSet 视图。  
Map.Entry<K,V>    pollFirstEntry()   
         移除并返回与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。  
Map.Entry<K,V>    pollLastEntry()   
         移除并返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。  
V   put(K key, V value)   
         将指定值与此映射中的指定键进行关联。  
void    putAll(Map<? extends K,? extends V> map)   
         将指定映射中的所有映射关系复制到此映射中。  
V   remove(Object key)   
         如果此 TreeMap 中存在该键的映射关系，则将其删除。  
int size()   
         返回此映射中的键-值映射关系数。  
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)   
         返回此映射的部分视图，其键的范围从 fromKey 到 toKey。  
SortedMap<K,V>    subMap(K fromKey, K toKey)   
         返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。  
SortedMap<K,V>    tailMap(K fromKey)   
         返回此映射的部分视图，其键大于等于 fromKey。  
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)   
         返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。  
Collection<V> values()   
         返回此映射包含的值的 Collection 视图。

AC代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;
public class Main{
	public static class Work{
		int key;
		int value;
	}
	public static class NodeComparator implements Comparator<Work>{

		@Override
		public int compare(Work o1, Work o2) {
			if(o1.key == o2.key)
				return o2.value - o1.value;
			else
				return o1.key - o2.key;
		}
		
	}
	public static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws Exception{
		String [] s = bf.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int m = Integer.parseInt(s[1]);
		Work [] w = new Work[n];
		for(int i=0;i<n;i++) {
			w[i] = new Work();
			s = bf.readLine().split(" ");
			w[i].key = Integer.parseInt(s[0]);
			w[i].value = Integer.parseInt(s[1]);
		}
		
		int [] friends = new int[m];
		s = bf.readLine().split(" ");
		for(int i = 0;i<m;i++) {
			friends[i] = Integer.parseInt(s[i]);
		}
		
		Arrays.sort(w,new NodeComparator());
//		for(int i=0;i<m;i++) {
//			int key = friends[i];
//			int value = 0;
//			for(int j=0;j<n && key >= w[j].key;j++) {
//				value = Math.max(value,w[j].value);
//			}
//			System.out.println(value);
//		}
//		O(n2)超时，所以采用有序表，有序表的操作均为O(logN)
		TreeMap<Integer,Integer> map = new TreeMap<>();
		map.put(w[0].key, w[0].value);
		Work pre = w[0];
		for(int i=1;i<n;i++) {
			if(w[i].key != pre.key && w[i].value > pre.value) {
				pre = w[i];
				map.put(w[i].key, w[i].value);
			}
		}
//		for(int i=0;i<m;i++) {
//			Integer key = map.floorKey(friends[i]);
//			int value = key!=null?map.get(key):0;
//			System.out.println(value);
//		}
		for(int i=0;i<m;i++) {
			int key = friends[i];
			int value = 0;
			for(int j=0;j<n && key >= w[j].key;j++) {
				value = Math.max(value,w[j].value);
			}
			System.out.println(value);
		}
	}
	
}