网站开发中 整体框架的架构,为什么网站百度搜不到,佛山品牌网站设计,wordpress朗读功能Problem: 503. 借教室 文章目录 思路解题方法复杂度Code 思路 这是一个二分查找问题。我们需要找到最大的借教室数量#xff0c;使得每个教室的借用时间不超过其可用时间。我们可以通过二分查找来找到这个最大的借教室数量。 解题方法 我们首先对所有的借教室请求按照结束时间… Problem: 503. 借教室 文章目录 思路解题方法复杂度Code 思路 这是一个二分查找问题。我们需要找到最大的借教室数量使得每个教室的借用时间不超过其可用时间。我们可以通过二分查找来找到这个最大的借教室数量。 解题方法 我们首先对所有的借教室请求按照结束时间进行排序。然后我们使用二分查找来找到最大的借教室数量。对于每个借教室数量我们检查是否所有的教室都可以在其可用时间内完成借用。我们使用一个差分数组来记录每个教室的借用时间。对于每个借教室请求我们在其开始时间处加上借用时间然后在其结束时间后一天减去借用时间。然后我们从前到后累加差分数组如果某一天的累加值超过了教室的可用时间那么这个借教室数量就不可行。 复杂度
时间复杂度: O ( n l o g n ) O(n log n) O(nlogn)其中 n 是借教室请求的数量。我们需要对所有的请求进行排序然后对每个可能的借教室数量进行检查。 空间复杂度: O ( n ) O(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;}}
