Acwing 503. 借教室

Problem: 503. 借教室

思路

这是一个二分查找问题。我们需要找到最大的借教室数量，使得每个教室的借用时间不超过其可用时间。我们可以通过二分查找来找到这个最大的借教室数量。

解题方法

我们首先对所有的借教室请求按照结束时间进行排序。然后我们使用二分查找来找到最大的借教室数量。对于每个借教室数量，我们检查是否所有的教室都可以在其可用时间内完成借用。我们使用一个差分数组来记录每个教室的借用时间。对于每个借教室请求，我们在其开始时间处加上借用时间，然后在其结束时间后一天减去借用时间。然后我们从前到后累加差分数组，如果某一天的累加值超过了教室的可用时间，那么这个借教室数量就不可行。

复杂度

时间复杂度:

$O(nlogn)$，其中 n 是借教室请求的数量。我们需要对所有的请求进行排序，然后对每个可能的借教室数量进行检查。

空间复杂度:

$O(n)$，我们需要使用一个差分数组来记录每个教室的借用时间。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = (int) 1e6 + 10;static int[] w = new int[MAXN];static long[] dif = new long[MAXN];static int[][] rent = new int[MAXN][3];static int n, m;public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();for (int i = 1; i <= n; i++) {w[i] = nextInt();}for (int i = 1; i <= m; i++) {rent[i][2] = nextInt();rent[i][0] = nextInt();rent[i][1] = nextInt();}int l = 0, r = m;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) {l = mid;} else {r = mid - 1;}}if (r == m) {out.println(0);} else {out.println(-1);out.println(r + 1);}out.flush();}private static boolean check(int mid) {// TODO Auto-generated method stubArrays.fill(dif, 0);for(int i = 1; i <= mid; i++) {dif[rent[i][0]] += rent[i][2];dif[rent[i][1] + 1] -= rent[i][2];}for(int i = 1; i <= n; i++) {dif[i] += dif[i - 1];if(dif[i] > w[i]) {return false;}}return true;}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}