分享丨qq
40
发布于 江西

import java.util.Arrays;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNextInt()) {

int n = in.nextInt();

int[] left = new int[n];

int[] right = new int[n];

for (int i = 0; i < n; i++) {

left[i] = in.nextInt();

right[i] = in.nextInt();

}

System.out.println(solve(left, right));

}

}

static int solve(int[] left, int[] right) {

int n = left.length;

int[] coordinates = new int[n * 2];

for (int i = 0; i < n; i++) {

coordinates[i * 2] = left[i];

coordinates[i * 2 + 1] = right[i];

}

Arrays.sort(coordinates);

int size = 0;

for (int i = 0; i < coordinates.length; i++) {

if (size == 0 || coordinates[i] != coordinates[size - 1]) {

coordinates[size++] = coordinates[i];

}

}

for (int i = 0; i < n; i++) {

left[i] = Arrays.binarySearch(coordinates, 0, size, left[i]);

right[i] = Arrays.binarySearch(coordinates, 0, size, right[i]);

}

SegmentTree tree = new SegmentTree(size);

int start = 0;

int answer = 0;

for (int end = 0; end < n; end++) {

tree.add(left[end], right[end], 1);

// 至少有“窗口长度 - 1”条记录包含同一个整数。

while (tree.max[1] < end - start) {

tree.add(left[start], right[start], -1);

start++;

}

answer = Math.max(answer, end - start + 1);

}

return answer;

}

static class SegmentTree {

final int size;

final int[] max;

final int[] lazy;

SegmentTree(int size) {

this.size = size;

max = new int[size * 4 + 5];

lazy = new int[size * 4 + 5];

}

void add(int left, int right, int value) {

add(1, 0, size - 1, left, right, value);

}

void add(int node, int low, int high,

int left, int right, int value) {

if (left <= low && high <= right) {

max[node] += value;

lazy[node] += value;

return;

}

int mid = (low + high) >>> 1;

if (left <= mid) {

add(node * 2, low, mid, left, right, value);

}

if (right > mid) {

add(node * 2 + 1, mid + 1, high, left, right, value);

}

max[node] = lazy[node]

+ Math.max(max[node * 2], max[node * 2 + 1]);

}

}

}

评论 (0)