How to Succeed in Algorithms Interview Series
Applications of Sweep Line Algorithm
- pre-sort (by x), so we can easily scan them
- or use TreeMap/TreeSet to store them
- calculate when meet open/end events
- Greedy
- Maintain max-end
- Maintain active sets
- using TreeMap, sort by y (different criteria)
Examples of Sweep Line Algorithm
- LeetCode 759 - Employee Free Time
- LeetCode 253 - Meeting Rooms II: find the minimum number of conference rooms required
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
TreeMap<Integer, Integer> times = new TreeMap<>();
for (Interval i : intervals) {
times.put(i.start, times.getOrDefault(i.start, 0) + 1);
times.put(i.end, times.getOrDefault(i.end, 0) - 1);
}
int count = 0, res = 0;
for (int c : times.values()) {
count += c;
res = Math.max(res, count);
}
return res;
}public List<int[]> getSkyline(int[][] buildings) {
List<int[]> heights = new ArrayList<>();
for (int[] b: buildings) {
heights.add(new int[]{b[0], - b[2]});
heights.add(new int[]{b[1], b[2]});
}
Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
heightMap.put(0,1);
int prevHeight = 0;
List<int[]> skyLine = new LinkedList<>();
for (int[] h: heights) {
if (h[1] < 0) {
Integer cnt = heightMap.get(-h[1]);
cnt = ( cnt == null ) ? 1 : cnt + 1;
heightMap.put(-h[1], cnt);
} else {
Integer cnt = heightMap.get(h[1]);
if (cnt == 1) {
heightMap.remove(h[1]);
} else {
heightMap.put(h[1], cnt - 1);
}
}
int currHeight = heightMap.firstKey();
if (prevHeight != currHeight) {
skyLine.add(new int[]{h[0], currHeight});
prevHeight = currHeight;
}
}
return skyLine;
}- LeetCode 452 - Minimum Number of Arrows to Burst Balloons
- Closest Pair of Points
- We sort the list of points from left to right in the x axis
- And then for each point :
- We remove from the candidates all the point that are further in x axis that the current min distance
- We take all the candidates that are located more or less current min distance from the current point in y axis
- We test for the min distance all the founded candidates with the current point
- And finally we add the current point to the list of candidates
- We remove from the candidates all the point that are further in x axis that the current min distance
- We sort the list of points from left to right in the x axis
- Given n line segments, find if any two segments intersect
- active line segments (line segments for which left end point is seen, but right end point is not seen yet)
- presort and TreeMap
- active line segments (line segments for which left end point is seen, but right end point is not seen yet)
- Find count of overlapping rectangles
- LeetCode 850 - Rectangle Area II (Union Of Rectangles)
- the active set contains only the rectangles which intersect the sweep line (rectangles whose left edges are visited but right edges are not)
- https://leetcode.com/problems/rectangle-area-ii/discuss/188832/Java-Line-Sweep-With-Sub-Class-Interval
- the active set contains only the rectangles which intersect the sweep line (rectangles whose left edges are visited but right edges are not)
- Convex Hull
