1
public ListNode mergeKLists(ListNode[] lists) {
2
    // 小根堆
3
    PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
4
        @Override
5
        public int compare(ListNode o1, ListNode o2) {
6
            return o1.val - o2.val;
7
        }
8
    });
9

10
    // 把所有链表的头节点加入小根堆
11
    for (ListNode node : lists) {
12
        if (node != null) {
13
            queue.add(node);
14
        }
15
    }
16

17
    if (queue.isEmpty()) {
18
        return null;
19
    }
20

21
    ListNode top = queue.poll();
22
    if (top.next != null) {
23
        queue.add(top.next);
24
    }
25

26
    ListNode result = top;
27
    ListNode now = top;
28

29
    while (!queue.isEmpty()) {
30
        top = queue.poll();
31
        now.next = top;
32
        now = top;
33

34
        if (top.next != null) {
35
            queue.add(top.next);
36
        }
37
    }
38

39
    return result;
40
}

1
public class Main {
2

3
    public static int MaxN = 100000;
4
    public static int[][] line = new int[MaxN][2];
5
    public static int n;
6

7
    public static int[] heap = new int[MaxN];
8
    public static int size = 0;
9

10
    public static void main(String[] args) throws IOException {
11
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
12
        StreamTokenizer in = new StreamTokenizer(br);
13
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
14

15
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
16
            n = (int) in.nval;
17
            for (int i = 0; i < n; i++) {
18
                in.nextToken();
19
                line[i][0] = (int) in.nval;
20
                in.nextToken();
21
                line[i][1] = (int) in.nval;
22
            }
23
            out.println(compute());
24
        }
25

26
        out.flush();
27
        out.close();
28
        br.close();
29
    }
30

31
    private static int compute() {
32
        // 首先将所有的线段按照左边界从小到大排好序
33
        // 然后利用小根堆，将右边界大于当前线段左边界的线段放入小根堆中
34
        // 此时小根堆有多少条记录，就是跟当前线段有重合的线段数目
35
        size = 0;
36
        int ans = 0;
37

38
        Arrays.sort(line, 0, n, new Comparator<int[]>() {
39
            @Override
40
            public int compare(int[] o1, int[] o2) {
41
                return o1[0] - o2[0];
42
            }
43
        });
44

45
        for (int i = 0; i < n; i++) {
46
            while (size > 0 && heap[0] <= line[i][0]) {
47
                pop();
48
            }
49
            add(line[i][1]);
50
            ans = Math.max(ans, size);
51
        }
52

53
        return ans;
54
    }
55

56
    private static void add(int i) {
57
        heap[size] = i;
58
        int index = size++;
59

60
        while (heap[index] < heap[(index - 1) / 2]) {
61
            swap(index, (index - 1) / 2);
62
            index = (index - 1) / 2;
63
        }
64
    }
65

66
    private static void pop() {
67
        swap(0, --size);
68
        int now = 0, l = 1;
69

70
        while (l < size) {
71
            int best = l + 1 < size && heap[l + 1] < heap[l] ? l + 1 : l;
72
            if (heap[best] > heap[now]) {
73
                return;
74
            }
75
            swap(best, now);
76
            now = best;
77
            l = now * 2 + 1;
78
        }
79
    }
80

81
    public static void swap(int a, int b) {
82
        int temp = heap[b];
83
        heap[b] = heap[a];
84
        heap[a] = temp;
85
    }
86
}