Skip to content

Commit f59b4c8

Browse files
unicoder88unicoder88
committed
Merge branch 'p757'
2 parents 0814caa + de6568e commit f59b4c8

2 files changed

Lines changed: 240 additions & 0 deletions

File tree

‎src/main/java/com/rkabanov/leetcode/p757/Solution.java‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package com.rkabanov.leetcode.p757;
2+
3+
import java.util.*;
4+
import java.util.stream.Collectors;
5+
6+
public class Solution {
7+
public int intersectionSizeTwo(int[][] intervals) {
8+
// 3000 intervals
9+
// shortest intervals first
10+
Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
11+
System.out.println("Sorted " + Arrays.deepToString(intervals));
12+
Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[1] - interval[0]));
13+
System.out.println("Sorted " + Arrays.deepToString(intervals));
14+
15+
HashSet<Integer> resultNumbers = new HashSet<>();
16+
17+
List<int[]> intervalList = new ArrayList<>(List.of(intervals));
18+
19+
// pick most frequent unused number, remove intervals with 2+ numbers
20+
while (!intervalList.isEmpty()) {
21+
int bestNumber = mostFrequentNumber(intervalList, resultNumbers);
22+
resultNumbers.add(bestNumber);
23+
24+
// remove possible intervals that now contain new numbers from result numbers
25+
intervalList = remainingIntervals(intervalList, resultNumbers);
26+
System.out.println("Remaining " + Arrays.deepToString(intervals));
27+
}
28+
29+
System.out.println("Result set: " + resultNumbers);
30+
31+
return resultNumbers.size();
32+
}
33+
34+
List<int[]> remainingIntervals(List<int[]> intervals, Set<Integer> resultNumbers) {
35+
if (resultNumbers.size() < 2) {
36+
// interval can be removed after at least 2 numbers picked
37+
return intervals;
38+
}
39+
40+
return intervals.stream()
41+
.filter(interval -> {
42+
int from = interval[0];
43+
int to = interval[1];
44+
45+
int matches = 0;
46+
for (int num : resultNumbers) {
47+
if (num >= from && num <= to) {
48+
matches++;
49+
if (matches >= 2) {
50+
// remove this interval
51+
System.out.println(" Removing interval [" + from + ", " + to + "]");
52+
return false;
53+
}
54+
}
55+
}
56+
57+
return true;
58+
})
59+
.collect(Collectors.toList());
60+
}
61+
62+
HashMap<Integer, Integer> calculateHistogram(List<int[]> intervals, Set<Integer> resultNumbers) {
63+
// overlap all intervals and count each number frequency
64+
HashMap<Integer, Integer> result = new HashMap<>();
65+
66+
for (int[] interval : intervals) {
67+
for (int num = interval[0]; num <= interval[1]; num++) {
68+
if (resultNumbers.contains(num)) {
69+
continue;
70+
}
71+
result.merge(num, 1, Integer::sum);
72+
}
73+
74+
}
75+
76+
return result;
77+
}
78+
79+
int mostFrequentNumber(List<int[]> intervals, Set<Integer> resultNumbers) {
80+
Map<Integer, Integer> histogram = calculateHistogram(intervals, resultNumbers);
81+
System.out.println(" Histogram: " + histogram);
82+
83+
// key with max value
84+
Map.Entry<Integer, Integer> bestEntry = Collections.max(histogram.entrySet(), Map.Entry.comparingByValue());
85+
System.out.println(" Best number " + bestEntry.getKey() + " with frequency " + bestEntry.getValue() );
86+
return bestEntry.getKey();
87+
}
88+
}

‎src/test/java/com/rkabanov/leetcode/p757/SolutionTest.java‎

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
1+
package com.rkabanov.leetcode.p757;
2+
3+
import org.junit.jupiter.api.Test;
4+
5+
import static org.junit.jupiter.api.Assertions.*;
6+
7+
public class SolutionTest {
8+
@Test
9+
public void testExample1() {
10+
var solution = new Solution();
11+
int result = solution.intersectionSizeTwo(new int[][]{
12+
{1, 3},
13+
{3, 7},
14+
{8, 9},
15+
});
16+
assertEquals(5, result);
17+
}
18+
19+
@Test
20+
public void testExample2() {
21+
var solution = new Solution();
22+
int result = solution.intersectionSizeTwo(new int[][]{
23+
{1, 3},
24+
{1, 4},
25+
{2, 5},
26+
{3, 5},
27+
});
28+
assertEquals(3, result);
29+
}
30+
31+
@Test
32+
public void testExample3() {
33+
var solution = new Solution();
34+
int result = solution.intersectionSizeTwo(new int[][]{
35+
{1, 2},
36+
{2, 3},
37+
{2, 4},
38+
{4, 5},
39+
});
40+
assertEquals(5, result);
41+
}
42+
43+
@Test
44+
public void testSolution4() {
45+
var solution = new Solution();
46+
int result = solution.intersectionSizeTwo(new int[][]{
47+
{6, 21},
48+
{1, 15},
49+
{15, 20},
50+
{10, 21},
51+
{0, 7},
52+
});
53+
assertEquals(4, result);
54+
}
55+
56+
@Test
57+
public void testSolution5() {
58+
var solution = new Solution();
59+
int result = solution.intersectionSizeTwo(new int[][]{
60+
{0, 10},
61+
{0, 2},
62+
{2, 10},
63+
{0, 6},
64+
{0, 5},
65+
{4, 8},
66+
{0, 3},
67+
{6, 8},
68+
{1, 10},
69+
{0, 1},
70+
});
71+
assertEquals(4, result);
72+
}
73+
74+
@Test
75+
public void testSolution6() {
76+
var solution = new Solution();
77+
int result = solution.intersectionSizeTwo(new int[][]{
78+
{2, 15},
79+
{9, 17},
80+
{0, 6},
81+
{17, 25},
82+
{0, 25},
83+
});
84+
assertEquals(5, result);
85+
}
86+
87+
@Test
88+
public void testSolution7() {
89+
var solution = new Solution();
90+
int result = solution.intersectionSizeTwo(new int[][]{
91+
{5, 25},
92+
{11, 15},
93+
{13, 23},
94+
{1, 2},
95+
{5, 8},
96+
{4, 13},
97+
{2, 6},
98+
{8, 12},
99+
{3, 8},
100+
{2, 23},
101+
{8, 16},
102+
{9, 22},
103+
{15, 21},
104+
{2, 21},
105+
{2, 14},
106+
{9, 19},
107+
{10, 18},
108+
{7, 18},
109+
{12, 21},
110+
{9, 16},
111+
{11, 13},
112+
{7, 18},
113+
{16, 19},
114+
{4, 25},
115+
{16, 19},
116+
});
117+
assertEquals(8, result);
118+
}
119+
120+
@Test
121+
public void testSolution8() {
122+
var solution = new Solution();
123+
int result = solution.intersectionSizeTwo(new int[][]{
124+
{12, 21},
125+
{11, 15},
126+
{5, 9},
127+
{6, 21},
128+
{12, 23},
129+
{1, 12},
130+
{4, 10},
131+
{16, 23},
132+
{5, 13},
133+
{13, 23},
134+
{20, 22},
135+
{7, 14},
136+
{2, 18},
137+
{18, 25},
138+
{4, 25},
139+
{22, 25},
140+
{3, 7},
141+
{2, 23},
142+
{6, 15},
143+
{11, 17},
144+
{14, 24},
145+
{12, 15},
146+
{14, 20},
147+
{1, 3},
148+
{5, 11},
149+
});
150+
assertEquals(9, result);
151+
}
152+
}

0 commit comments

Comments
 (0)