[fb 面经] intervals sweep line

intervals sweep line"/>

[fb 面经] intervals sweep line

Leetcode 上的题

Merge Intervals

Insert Intervals

Meeting Rooms

Meeting RoomsII

Topcoder tutorial:

Sweep Line Algorithms

some from gitbook about sweep line problems on leetcode:

.html

面经：

题1：

Given an array of intervals in a line consisting of start and end points
[[s1,e1],[s2,e2],...] (si < ei), find any point that is covered by most
intervals.
code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** Given an array of intervals in a line consisting of start and end points* [[s1,e1],[s2,e2],...] (si < ei), find any point that is covered by most* intervals.*/
public class IntervalCover {public static class Interval {int start;int end;Interval(int start, int end) {this.start = start;this.end = end;}}public int getDensity(List<Interval> intervals) {int[] starts = new int[intervals.size()];int[] ends = new int[intervals.size()];for (int i = 0; i < starts.length; i++) {starts[i] = intervals.get(i).start;ends[i] = intervals.get(i).end;}Arrays.sort(starts);Arrays.sort(ends);int end = 0;int ans = 0;for (int i = 0; i < starts.length; i++) {if (starts[i] >= ends[end]) {end++;} else {ans = starts[i];}}return ans;}public static void main(String[] args) {// String input = "[[0,30],[5,10],[15,20]]";// String input = "[[7,10],[2,4]]";// String input = "[[5,8],[6,8]]";// String input = "[[13,15],[1,13]]";String input = "[[2,7]]";List<Interval> intervals = new ArrayList<Interval>();for (String str : input.substring(2, input.length() - 2).split("\\],\\[")) {String[] strs = str.split(",");intervals.add(new Interval(Integer.valueOf(strs[0]), Integer.valueOf(strs[1])));}System.out.println(new IntervalCover().getDensity(intervals));}
}

题2：

Given an array of rectangles consisting of left top and right down points
[[x1,y1, x2, y2],[x3,y3,x4,y4],...] , find any point that is covered by most
rectangles.

public class IntervalD2 {public static class Rectangle {int x1;int y1;int x2;int y2;Rectangle(int x1, int y1, int x2, int y2) {this.x1 = x1;this.x2 = x2;this.y1 = y1;this.y2 = y2;}@Overridepublic String toString() {return x1 + "|" + y1 + "|" + x2 + "|" + y2;}}public int[] getArea(List<Rectangle> rects) {Set<Integer> ys = new HashSet<Integer>();Map<Integer, List<Rectangle>> map = new HashMap<Integer, List<Rectangle>>();for (Rectangle rect : rects) {ys.add(rect.y1);ys.add(rect.y2);List<Rectangle> list = map.getOrDefault(rect.y1, new ArrayList<>());list.add(rect);map.put(rect.y1, list);list = map.getOrDefault(rect.y2, new ArrayList<>());list.add(rect);map.put(rect.y2, list);}List<Integer> yList = new ArrayList<Integer>(ys);Collections.sort(yList);PriorityQueue<Rectangle> pq = new PriorityQueue<Rectangle>((o1, o2) -> Integerpare(o1.y2, o2.y2));int ans = 0;int ans_x = 0;int ans_y = 0;for (int y : yList) {List<Rectangle> list = map.get(y);if (list == null) {continue;}for (Rectangle rect : list) {if (rect.y1 == y) {pq.add(rect);}}int[] starts = new int[pq.size()];int[] ends = new int[pq.size()];int counter = 0;System.out.println(pq.toString());for (Rectangle rect : pq) {starts[counter] = rect.x1;ends[counter++] = rect.x2;}Arrays.sort(starts);Arrays.sort(ends);int r = 0;int index = 0;int pos = 0;for (int i = 0; i < starts.length; i++) {if (starts[i] < ends[index]) {r++;pos = ends[index];} else {index++;}}if (r > ans) {ans = r;ans_x = pos;ans_y = y;}while (!pq.isEmpty() && pq.peek().y2 <= y) {pq.poll();}}return new int[] {ans_x, ans_y, ans};}public static void main(String[] args) {String input = "[[1,1,4,4],[3,3,4,4],[2,4,6,6],[7,7,8,8]]";List<Rectangle> rects = new ArrayList<Rectangle>();for (String rect : input.substring(2, input.length() - 2).split("\\],\\[")) {String[] strs = rect.split(",");rects.add(new Rectangle(Integer.valueOf(strs[0]), Integer.valueOf(strs[1]), Integer.valueOf(strs[2]), Integer.valueOf(strs[3])));}System.out.println(Arrays.toString(new IntervalD2().getArea(rects)));}
}

题3：

Given an array of rectangles consisting of left top and right down points
[[x1,y1, x2, y2],[x3,y3,x4,y4],...] , find the area covered by all these rectangles.

import com.sun.scenario.effect.impl.state.LinearConvolveKernel;import java.util.*;/****/
public class IntervalD2 {public static class Rectangle {int x1;int y1;int x2;int y2;Rectangle(int x1, int y1, int x2, int y2) {this.x1 = x1;this.x2 = x2;this.y1 = y1;this.y2 = y2;}@Overridepublic String toString() {return x1 + "|" + y1 + "|" + x2 + "|" + y2;}}public int getArea2(List<Rectangle> rects) {int ans = 0;Set<Integer> ys = new HashSet<Integer>();Map<Integer, List<Rectangle>> map = new HashMap<Integer, List<Rectangle>>();for (Rectangle rect : rects) {ys.add(rect.y1);ys.add(rect.y2);List<Rectangle> list = map.getOrDefault(rect.y1, new ArrayList<>());list.add(rect);map.put(rect.y1, list);list = map.getOrDefault(rect.y2, new ArrayList<>());list.add(rect);map.put(rect.y2, list);}System.out.println(map.toString());List<Integer> yList = new ArrayList<Integer>(ys);Collections.sort(yList);System.out.println(yList.toString());PriorityQueue<Rectangle> pq = new PriorityQueue<Rectangle>((o1, o2) -> Integerpare(o1.y2, o2.y2));for (int i = 0; i < yList.size(); i++) {int y = yList.get(i);List<Rectangle> list = map.get(y);if (list == null) {continue;}System.out.println(pq.toString());if (!pq.isEmpty()) {int[] starts = new int[pq.size()];int[] ends = new int[pq.size()];int counter = 0;int deltaY = yList.get(i) - yList.get(i - 1);for (Rectangle rect : pq) {starts[counter] = rect.x1;ends[counter++] = rect.x2;}Arrays.sort(starts);Arrays.sort(ends);int a = 0;int b = 0;int r = 0;while (a < starts.length) {if (starts[a] < ends[b]) {if (r == 0) {ans += (ends[b] - starts[a]) * deltaY;System.out.println("ans: " + ans);}a++;r++;} else {r--;b++;}}while (!pq.isEmpty() && pq.peek().y2 == y) {pq.poll();}}for (Rectangle rect : list) {if (rect.y1 == y) {pq.add(rect);}}}return ans;}public static void main(String[] args) {String input = "[[1,1,4,4],[3,3,4,4],[4,4,6,6],[7,7,8,8]]";List<Rectangle> rects = new ArrayList<Rectangle>();for (String rect : input.substring(2, input.length() - 2).split("\\],\\[")) {String[] strs = rect.split(",");rects.add(new Rectangle(Integer.valueOf(strs[0]), Integer.valueOf(strs[1]), Integer.valueOf(strs[2]), Integer.valueOf(strs[3])));}System.out.println(new IntervalD2().getArea2(rects));}
}

转载于:.html