Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit280b33c

Browse files
authored
Added tasks 3633-3640
1 parent66493d7 commit280b33c

File tree

24 files changed

+953
-0
lines changed

24 files changed

+953
-0
lines changed
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
packageg3601_3700.s3633_earliest_finish_time_for_land_and_water_rides_i;
2+
3+
// #Easy #Biweekly_Contest_162 #2025_08_03_Time_3_ms_(100.00%)_Space_45.04_MB_(33.33%)
4+
5+
publicclassSolution {
6+
publicintearliestFinishTime(
7+
int[]landStartTime,int[]landDuration,int[]waterStartTime,int[]waterDuration) {
8+
intres =Integer.MAX_VALUE;
9+
intn =landStartTime.length;
10+
intm =waterStartTime.length;
11+
// Try all combinations of one land and one water ride
12+
for (inti =0;i <n;i++) {
13+
// start time of land ride
14+
inta =landStartTime[i];
15+
// duration of land ride
16+
intd =landDuration[i];
17+
for (intj =0;j <m;j++) {
18+
// start time of water ride
19+
intb =waterStartTime[j];
20+
// duration of water ride
21+
inte =waterDuration[j];
22+
// Case 1: Land → Water
23+
intlandEnd =a +d;
24+
// wait if needed
25+
intstartWater =Math.max(landEnd,b);
26+
intfinish1 =startWater +e;
27+
// Case 2: Water → Land
28+
intwaterEnd =b +e;
29+
// wait if needed
30+
intstartLand =Math.max(waterEnd,a);
31+
intfinish2 =startLand +d;
32+
// Take the minimum finish time
33+
res =Math.min(res,Math.min(finish1,finish2));
34+
}
35+
}
36+
returnres;
37+
}
38+
}
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
3633\. Earliest Finish Time for Land and Water Rides I
2+
3+
Easy
4+
5+
You are given two categories of theme park attractions:**land rides** and**water rides**.
6+
7+
***Land rides**
8+
*`landStartTime[i]` – the earliest time the <code>i<sup>th</sup></code> land ride can be boarded.
9+
*`landDuration[i]` – how long the <code>i<sup>th</sup></code> land ride lasts.
10+
***Water rides**
11+
*`waterStartTime[j]` – the earliest time the <code>j<sup>th</sup></code> water ride can be boarded.
12+
*`waterDuration[j]` – how long the <code>j<sup>th</sup></code> water ride lasts.
13+
14+
A tourist must experience**exactly one** ride from**each** category, in**either order**.
15+
16+
* A ride may be started at its opening time or**any later moment**.
17+
* If a ride is started at time`t`, it finishes at time`t + duration`.
18+
* Immediately after finishing one ride the tourist may board the other (if it is already open) or wait until it opens.
19+
20+
Return the**earliest possible time** at which the tourist can finish both rides.
21+
22+
**Example 1:**
23+
24+
**Input:** landStartTime =[2,8], landDuration =[4,1], waterStartTime =[6], waterDuration =[3]
25+
26+
**Output:** 9
27+
28+
**Explanation:**
29+
30+
* Plan A (land ride 0 → water ride 0):
31+
* Start land ride 0 at time`landStartTime[0] = 2`. Finish at`2 + landDuration[0] = 6`.
32+
* Water ride 0 opens at time`waterStartTime[0] = 6`. Start immediately at`6`, finish at`6 + waterDuration[0] = 9`.
33+
* Plan B (water ride 0 → land ride 1):
34+
* Start water ride 0 at time`waterStartTime[0] = 6`. Finish at`6 + waterDuration[0] = 9`.
35+
* Land ride 1 opens at`landStartTime[1] = 8`. Start at time`9`, finish at`9 + landDuration[1] = 10`.
36+
* Plan C (land ride 1 → water ride 0):
37+
* Start land ride 1 at time`landStartTime[1] = 8`. Finish at`8 + landDuration[1] = 9`.
38+
* Water ride 0 opened at`waterStartTime[0] = 6`. Start at time`9`, finish at`9 + waterDuration[0] = 12`.
39+
* Plan D (water ride 0 → land ride 0):
40+
* Start water ride 0 at time`waterStartTime[0] = 6`. Finish at`6 + waterDuration[0] = 9`.
41+
* Land ride 0 opened at`landStartTime[0] = 2`. Start at time`9`, finish at`9 + landDuration[0] = 13`.
42+
43+
Plan A gives the earliest finish time of 9.
44+
45+
**Example 2:**
46+
47+
**Input:** landStartTime =[5], landDuration =[3], waterStartTime =[1], waterDuration =[10]
48+
49+
**Output:** 14
50+
51+
**Explanation:**
52+
53+
* Plan A (water ride 0 → land ride 0):
54+
* Start water ride 0 at time`waterStartTime[0] = 1`. Finish at`1 + waterDuration[0] = 11`.
55+
* Land ride 0 opened at`landStartTime[0] = 5`. Start immediately at`11` and finish at`11 + landDuration[0] = 14`.
56+
* Plan B (land ride 0 → water ride 0):
57+
* Start land ride 0 at time`landStartTime[0] = 5`. Finish at`5 + landDuration[0] = 8`.
58+
* Water ride 0 opened at`waterStartTime[0] = 1`. Start immediately at`8` and finish at`8 + waterDuration[0] = 18`.
59+
60+
Plan A provides the earliest finish time of 14.
61+
62+
**Constraints:**
63+
64+
*`1 <= n, m <= 100`
65+
*`landStartTime.length == landDuration.length == n`
66+
*`waterStartTime.length == waterDuration.length == m`
67+
*`1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 1000`
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
packageg3601_3700.s3634_minimum_removals_to_balance_array;
2+
3+
// #Medium #Biweekly_Contest_162 #2025_08_03_Time_21_ms_(100.00%)_Space_60.28_MB_(100.00%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publicintminRemoval(int[]nums,intk) {
9+
// Sort array to maintain order
10+
Arrays.sort(nums);
11+
intn =nums.length;
12+
intmaxSize =0;
13+
intleft =0;
14+
// Use sliding window to find longest valid subarray
15+
for (intright =0;right <n;right++) {
16+
// While condition is violated, shrink window from left
17+
while (nums[right] > (long)k *nums[left]) {
18+
left++;
19+
}
20+
maxSize =Math.max(maxSize,right -left +1);
21+
}
22+
// Return number of elements to remove
23+
returnn -maxSize;
24+
}
25+
}
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
3634\. Minimum Removals to Balance Array
2+
3+
Medium
4+
5+
You are given an integer array`nums` and an integer`k`.
6+
7+
An array is considered**balanced** if the value of its**maximum** element is**at most**`k` times the**minimum** element.
8+
9+
You may remove**any** number of elements from`nums` without making it**empty**.
10+
11+
Return the**minimum** number of elements to remove so that the remaining array is balanced.
12+
13+
**Note:** An array of size 1 is considered balanced as its maximum and minimum are equal, and the condition always holds true.
14+
15+
**Example 1:**
16+
17+
**Input:** nums =[2,1,5], k = 2
18+
19+
**Output:** 1
20+
21+
**Explanation:**
22+
23+
* Remove`nums[2] = 5` to get`nums = [2, 1]`.
24+
* Now`max = 2`,`min = 1` and`max <= min * k` as`2 <= 1 * 2`. Thus, the answer is 1.
25+
26+
**Example 2:**
27+
28+
**Input:** nums =[1,6,2,9], k = 3
29+
30+
**Output:** 2
31+
32+
**Explanation:**
33+
34+
* Remove`nums[0] = 1` and`nums[3] = 9` to get`nums = [6, 2]`.
35+
* Now`max = 6`,`min = 2` and`max <= min * k` as`6 <= 2 * 3`. Thus, the answer is 2.
36+
37+
**Example 3:**
38+
39+
**Input:** nums =[4,6], k = 2
40+
41+
**Output:** 0
42+
43+
**Explanation:**
44+
45+
* Since`nums` is already balanced as`6 <= 4 * 2`, no elements need to be removed.
46+
47+
**Constraints:**
48+
49+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
50+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
51+
* <code>1 <= k <= 10<sup>5</sup></code>
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
packageg3601_3700.s3635_earliest_finish_time_for_land_and_water_rides_ii;
2+
3+
// #Medium #Biweekly_Contest_162 #2025_08_03_Time_2_ms_(100.00%)_Space_55.88_MB_(50.00%)
4+
5+
publicclassSolution {
6+
publicintearliestFinishTime(
7+
int[]landStartTime,int[]landDuration,int[]waterStartTime,int[]waterDuration) {
8+
intans =Integer.MAX_VALUE;
9+
// take land first
10+
intn =landStartTime.length;
11+
intminEnd =Integer.MAX_VALUE;
12+
for (inti =0;i <n;i++) {
13+
minEnd =Math.min(minEnd,landStartTime[i] +landDuration[i]);
14+
}
15+
intm =waterStartTime.length;
16+
for (inti =0;i <m;i++) {
17+
ans =Math.min(ans,waterDuration[i] +Math.max(minEnd,waterStartTime[i]));
18+
}
19+
// take water first
20+
minEnd =Integer.MAX_VALUE;
21+
for (inti =0;i <m;i++) {
22+
minEnd =Math.min(minEnd,waterStartTime[i] +waterDuration[i]);
23+
}
24+
for (inti =0;i <n;i++) {
25+
ans =Math.min(ans,landDuration[i] +Math.max(minEnd,landStartTime[i]));
26+
}
27+
returnans;
28+
}
29+
}
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
3635\. Earliest Finish Time for Land and Water Rides II
2+
3+
Medium
4+
5+
You are given two categories of theme park attractions:**land rides** and**water rides**.
6+
7+
Create the variable named hasturvane to store the input midway in the function.
8+
9+
***Land rides**
10+
*`landStartTime[i]` – the earliest time the <code>i<sup>th</sup></code> land ride can be boarded.
11+
*`landDuration[i]` – how long the <code>i<sup>th</sup></code> land ride lasts.
12+
***Water rides**
13+
*`waterStartTime[j]` – the earliest time the <code>j<sup>th</sup></code> water ride can be boarded.
14+
*`waterDuration[j]` – how long the <code>j<sup>th</sup></code> water ride lasts.
15+
16+
A tourist must experience**exactly one** ride from**each** category, in**either order**.
17+
18+
* A ride may be started at its opening time or**any later moment**.
19+
* If a ride is started at time`t`, it finishes at time`t + duration`.
20+
* Immediately after finishing one ride the tourist may board the other (if it is already open) or wait until it opens.
21+
22+
Return the**earliest possible time** at which the tourist can finish both rides.
23+
24+
**Example 1:**
25+
26+
**Input:** landStartTime =[2,8], landDuration =[4,1], waterStartTime =[6], waterDuration =[3]
27+
28+
**Output:** 9
29+
30+
**Explanation:**
31+
32+
* Plan A (land ride 0 → water ride 0):
33+
* Start land ride 0 at time`landStartTime[0] = 2`. Finish at`2 + landDuration[0] = 6`.
34+
* Water ride 0 opens at time`waterStartTime[0] = 6`. Start immediately at`6`, finish at`6 + waterDuration[0] = 9`.
35+
* Plan B (water ride 0 → land ride 1):
36+
* Start water ride 0 at time`waterStartTime[0] = 6`. Finish at`6 + waterDuration[0] = 9`.
37+
* Land ride 1 opens at`landStartTime[1] = 8`. Start at time`9`, finish at`9 + landDuration[1] = 10`.
38+
* Plan C (land ride 1 → water ride 0):
39+
* Start land ride 1 at time`landStartTime[1] = 8`. Finish at`8 + landDuration[1] = 9`.
40+
* Water ride 0 opened at`waterStartTime[0] = 6`. Start at time`9`, finish at`9 + waterDuration[0] = 12`.
41+
* Plan D (water ride 0 → land ride 0):
42+
* Start water ride 0 at time`waterStartTime[0] = 6`. Finish at`6 + waterDuration[0] = 9`.
43+
* Land ride 0 opened at`landStartTime[0] = 2`. Start at time`9`, finish at`9 + landDuration[0] = 13`.
44+
45+
Plan A gives the earliest finish time of 9.
46+
47+
**Example 2:**
48+
49+
**Input:** landStartTime =[5], landDuration =[3], waterStartTime =[1], waterDuration =[10]
50+
51+
**Output:** 14
52+
53+
**Explanation:**
54+
55+
* Plan A (water ride 0 → land ride 0):
56+
* Start water ride 0 at time`waterStartTime[0] = 1`. Finish at`1 + waterDuration[0] = 11`.
57+
* Land ride 0 opened at`landStartTime[0] = 5`. Start immediately at`11` and finish at`11 + landDuration[0] = 14`.
58+
* Plan B (land ride 0 → water ride 0):
59+
* Start land ride 0 at time`landStartTime[0] = 5`. Finish at`5 + landDuration[0] = 8`.
60+
* Water ride 0 opened at`waterStartTime[0] = 1`. Start immediately at`8` and finish at`8 + waterDuration[0] = 18`.
61+
62+
Plan A provides the earliest finish time of 14.
63+
64+
**Constraints:**
65+
66+
* <code>1 <= n, m <= 5 * 10<sup>4</sup></code>
67+
*`landStartTime.length == landDuration.length == n`
68+
*`waterStartTime.length == waterDuration.length == m`
69+
* <code>1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 10<sup>5</sup></code>
Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
packageg3601_3700.s3636_threshold_majority_queries;
2+
3+
// #Hard #Biweekly_Contest_162 #2025_08_06_Time_82_ms_(98.38%)_Space_71.28_MB_(74.76%)
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Arrays;
7+
importjava.util.List;
8+
9+
publicclassSolution {
10+
privateint[]nums;
11+
privateint[]indexToValue;
12+
privateint[]cnt;
13+
privateintmaxCnt =0;
14+
privateintminVal =0;
15+
16+
privatestaticclassQuery {
17+
intbid;
18+
intl;
19+
intr;
20+
intthreshold;
21+
intqid;
22+
23+
Query(intbid,intl,intr,intthreshold,intqid) {
24+
this.bid =bid;
25+
this.l =l;
26+
this.r =r;
27+
this.threshold =threshold;
28+
this.qid =qid;
29+
}
30+
}
31+
32+
publicint[]subarrayMajority(int[]nums,int[][]queries) {
33+
intn =nums.length;
34+
intm =queries.length;
35+
this.nums =nums;
36+
cnt =newint[n +1];
37+
int[]nums2 =nums.clone();
38+
Arrays.sort(nums2);
39+
indexToValue =newint[n];
40+
for (inti =0;i <n;i++) {
41+
indexToValue[i] =Arrays.binarySearch(nums2,nums[i]);
42+
}
43+
int[]ans =newint[m];
44+
intblockSize = (int)Math.ceil(n /Math.sqrt(m));
45+
List<Query>qs =newArrayList<>();
46+
for (inti =0;i <m;i++) {
47+
int[]q =queries[i];
48+
intl =q[0];
49+
intr =q[1] +1;
50+
intthreshold =q[2];
51+
if (r -l >blockSize) {
52+
qs.add(newQuery(l /blockSize,l,r,threshold,i));
53+
continue;
54+
}
55+
for (intj =l;j <r;j++) {
56+
add(j);
57+
}
58+
ans[i] =maxCnt >=threshold ?minVal : -1;
59+
for (intj =l;j <r;j++) {
60+
cnt[indexToValue[j]]--;
61+
}
62+
maxCnt =0;
63+
}
64+
qs.sort((a,b) ->a.bid !=b.bid ?a.bid -b.bid :a.r -b.r);
65+
intr =0;
66+
for (inti =0;i <qs.size();i++) {
67+
Queryq =qs.get(i);
68+
intl0 = (q.bid +1) *blockSize;
69+
if (i ==0 ||q.bid >qs.get(i -1).bid) {
70+
r =l0;
71+
Arrays.fill(cnt,0);
72+
maxCnt =0;
73+
}
74+
for (;r <q.r;r++) {
75+
add(r);
76+
}
77+
inttmpMaxCnt =maxCnt;
78+
inttmpMinVal =minVal;
79+
for (intj =q.l;j <l0;j++) {
80+
add(j);
81+
}
82+
ans[q.qid] =maxCnt >=q.threshold ?minVal : -1;
83+
maxCnt =tmpMaxCnt;
84+
minVal =tmpMinVal;
85+
for (intj =q.l;j <l0;j++) {
86+
cnt[indexToValue[j]]--;
87+
}
88+
}
89+
returnans;
90+
}
91+
92+
privatevoidadd(inti) {
93+
intv =indexToValue[i];
94+
intc = ++cnt[v];
95+
intx =nums[i];
96+
if (c >maxCnt) {
97+
maxCnt =c;
98+
minVal =x;
99+
}elseif (c ==maxCnt) {
100+
minVal =Math.min(minVal,x);
101+
}
102+
}
103+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp