Missing Test Case - 1235. Maximum Profit in Job Scheduling #19160
Description
LeetCode Username: aryan-k
1235. Maximum Profit in Job Scheduling
https://leetcode.com/problems/maximum-profit-in-job-scheduling/
Category of the bug
- Problem description
- Solved examples
- Problem constraints
- Problem hints
- Incorrect or missing "Related Topics"
- Incorrect test Case (Output of test case is incorrect as per the problem statement)
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
- Editorial
- Programming language support
Description of the bug
Missing testcase where startTime.length == endTime.length == profit.length = 1
I got a solution accepted which shouldn't have accepted.
Language used for code
Java
Code used for Submit/Run operation
// LIS+ binarySearch + segmentTree
// O(n log n)
//
class Solution {
public int jobScheduling(int[] start, int[] end, int[] profit) {
int n = start.length;
int[][] time = new int[n][3]; // accumulate all 3
for(int i=0; i<n; ++i)
time[i] = new int[]{start[i], end[i], profit[i]};
Arrays.sort(time, (a, b)->{
return a[1]==b[1] ? b[0]-a[0] : a[1]-b[1];
}); // sort based on end time
for(int i=0; i<n; ++i){
end[i] = time[i][1];
profit[i] = time[i][2];
}
int ans = 0;
SegmentTree seg = new SegmentTree(profit);
for(int i=1; i<n; ++i){
int idx = bs(end, 0, i-1, time[i][0]);
int mx = seg.query(0, idx);
profit[i] += mx;
seg.update(i, profit[i]);
ans = Math.max(ans, profit[i]);
}
return ans;
}
int bs(int[] nums, int i, int j, int x){
int ans = -1;
while(i<=j){
int mid = i + (j-i)/2;
if(nums[mid] <= x){
ans = mid;
i = mid + 1;
}
else
j = mid - 1;
}
return ans;
}
}
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] nums) {
n = nums.length;
int height = (int) (Math.ceil(Math.log(n) / Math.log(2)));
int mxSize = 2 * (int) Math.pow(2, height) - 1;
tree = new int[mxSize];
buildTree(nums, 0, 0, n - 1);
}
// or we can use 4*n as size
// tree = new int[4 * n];
private void buildTree(int[] nums, int index, int start, int end) {
if (start == end) {
tree[index] = nums[start];
return;
}
int mid = start + (end - start) / 2;
buildTree(nums, 2 * index + 1, start, mid);
buildTree(nums, 2 * index + 2, mid + 1, end);
tree[index] = Math.max(tree[2 * index + 1], tree[2 * index + 2]);
}
public int query(int left, int right) {
if(right < left) return 0;
return queryHelper(0, 0, n - 1, left, right);
}
private int queryHelper(int index, int start, int end, int left, int right) {
if (start > right || end < left) {
return Integer.MIN_VALUE;
}
if (start >= left && end <= right) {
return tree[index];
}
int mid = start + (end - start) / 2;
int leftMax = queryHelper(2 * index + 1, start, mid, left, right);
int rightMax = queryHelper(2 * index + 2, mid + 1, end, left, right);
return Math.max(leftMax, rightMax);
}
public void update(int index, int val) {
updateHelper(0, 0, n - 1, index, val);
}
private void updateHelper(int index, int start, int end, int idx, int val) {
if (start == end) {
tree[index] = val;
return;
}
int mid = start + (end - start) / 2;
if (idx <= mid) {
updateHelper(2 * index + 1, start, mid, idx, val);
} else {
updateHelper(2 * index + 2, mid + 1, end, idx, val);
}
tree[index] = Math.max(tree[2 * index + 1], tree[2 * index + 2]);
}
}Expected behavior
This type of testcase missing - [1] [3] [50]
Code shouldn't get accepted.
Screenshots
Additional context
My Submission - https://leetcode.com/submissions/detail/1138735751/
I used same code in Maximum Earnings From Taxi (which is exactly the same question), there same code didn't work. (It failed in Testcase #1).
