mcopes73
BAN USERThis concise function yields the max number of seats possible:
```
public static int countMaxPossibleAllocation(int[] seats) {
int count = 1, ans = 0;
for(int i = 0; i < seats.length; i++) {
if(seats[i] == 1) {
ans += (count - 1) / 2;
count = 0;
}else{
count++;
}
}
if(count > 0) ans += count / 2;
return ans;
}
```
Sort by starting time and traverse. Keep current ending point and sum so far.
public static int totalTimeOn(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
int ending = 0, ans = 0;
for(int[] i : intervals) {
ans += Math.max(i[1] - Math.max(i[0], ending), 0);
ending = Math.max(ending, i[1]);
}
return ans;
}
Check as you do a simultaneous preorder traversal.
Time: O(n)
Space: O(log(n))
Where n is the size of T1.
This is the most time & space efficient solution I could come up with. Can anyone think of a way to solve it using constant space?
- mcopes73 February 08, 2017