leetcode/code/lc1094.java at master · mJackie/leetcode · GitHub

History

44 lines (42 loc) · 1.41 KB

Raw

package code;

* 1094. Car Pooling

* 题意：

* 难度：Medium

* 分类：

* 思路： lc56 类似的题，但该题的集合没有传递覆盖的特性，所以遍历的时候又加了个循环，N^2

* 非常巧妙的方法，每次记录上车，下车人数，然后遍历一遍进行模拟上下车

* Tips：lc253, lc56

import java.util.Arrays;

import java.util.Comparator;

public class lc1094 {

public boolean carPooling(int[][] trips, int capacity) {

Arrays.sort(trips, new Comparator<int[]>() { // 记住这种写法

@Override

public int compare(int[] o1, int[] o2) {

if(o1[1]!=o2[1])

return o1[1] - o2[1];

else

return o2[2] - o1[2];

}

});

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

int current = trips[i][0];

for (int j = i-1; j >=0 ; j--) { //往前找是否重叠

if(trips[j][2]>trips[i][1]) current += trips[j][0];

}

if(current>capacity) return false;

}

return true;

}

public boolean carPooling2(int[][] trips, int capacity) {

int stops[] = new int[1001];

for (int t[] : trips) {

stops[t[1]] += t[0];

stops[t[2]] -= t[0];

}

for (int i = 0; capacity >= 0 && i < 1001; ++i) capacity -= stops[i];

return capacity >= 0;

}

leetcode/code/lc1094.java at master · mJackie/leetcode · GitHub

Expand file tree

Breadcrumbs

lc1094.java

Latest commit

History

Breadcrumbs

lc1094.java

File metadata and controls