题目路径

1847. 最近的房间

个人解法

关键点：

  1. 排序
  2. TreeSet（二分查找）
  3. 数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class ClosestRoom {  
    public int[] closestRoom(int[][] rooms, int[][] queries) {  
        return main(rooms , que);
    }  
  
    /**  
     * 满足条件的房间 id  
     * 例子：rooms = [[2,2],[1,2],[3,2]]  
     *      queries = [[3,1],[3,3],[5,2]]     * 结果：[3,-1,3]    * @param rooms  
     * @param querie  
     * @return  
     */  
    static class C1 {  
	    private int size;  
	    private int id;  
	    // 类型：0:房间，1：询问  
	    private int type;  
	    // 询问的下标  
	    private int querieIndex;  
	  
	    public C1(int type, int id, int size) {  
	        this.type = type;  
	        this.id = id;  
	        this.size = size;  
	    }  
	  
	    public int getSize() {  
	        return this.size;  
	    }  
	  
	    public boolean isQuerie() {  
	        return this.type == 1 ? true : false;  
	    }  
	  
	    public int getId() {  
	        return this.id;  
	    }  
	  
	    public void setQuerieIndex(int index) {  
	        this.querieIndex = index;  
	    }  
	  
	    public Integer getQuerieIndex() {  
	        return this.querieIndex;  
	    }  
	}  
	  
	public static int[] main(int[][] rooms, int[][] queries) {  
	    int[] result = new int[queries.length];  
	    List<C1> c1List = new ArrayList<>();  
	    for (int[] room : rooms) {  
	        C1 c1 = new C1(0, room[0], room[1]);  
	        c1List.add(c1);  
	    }  
	  
	    int index = 0;  
	    for (int[] querie : queries) {  
	        C1 c1 = new C1(1, querie[0], querie[1]);  
	        c1.setQuerieIndex(index);  
	        index++;  
	        c1List.add(c1);  
	    }  
	  
	    // 按照 size 进行排序  
	    Collections.sort(c1List, new Comparator<C1>() {  
	        @Override  
	        public int compare(C1 o1, C1 o2) {  
	            return Integer.compare(o2.getSize(), o1.getSize());  
	        }  
	    });  
	  
	    TreeSet<Integer> roomIdTree = new TreeSet<>();  
	    for (C1 c1 : c1List) {  
	        if (!c1.isQuerie()) {  
	            roomIdTree.add(c1.getId());  
	            continue;  
	        }  
	        result[c1.getQuerieIndex()] = getMinRoomId(roomIdTree, c1);  
	    }  
	    return result;  
	}  
	  
	// 查找最小的房间号  
	public static int getMinRoomId(TreeSet<Integer> roomIdTree, C1 c1) {  
	    if (roomIdTree.isEmpty()) {  
	        return -1;  
	    }  
        // 找出大于等于 c1.id 的最小的房间号
	    Integer ceiling = roomIdTree.ceiling(c1.getId());  
        // 找出小于等于 c1.id 的最大的房间号
	    Integer floor = roomIdTree.floor(c1.getId());  
	    if (ceiling == null){  
	        return floor;  
	    }else if (floor == null){  
	        return ceiling;  
	    }else{  
	        return Math.abs(ceiling - c1.getId()) >= Math.abs(floor - c1.getId()) ? floor : ceiling;  
	    }  
	} 
}