掃描線 — 範例詳解

// LC 253 - Meeting Rooms II
// IDEA: Sweep line — +1 on start, -1 on end; sort (end before start at ties); track peak
// time = O(N log N), space = O(N)
public int minMeetingRooms(int[][] intervals) {
    List<int[]> events = new ArrayList<>();
    for (int[] inv : intervals) {
        events.add(new int[]{inv[0], 1});
        events.add(new int[]{inv[1], -1});
    }
    events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); // end before start at same time
    int rooms = 0, maxRooms = 0;
    for (int[] e : events) { rooms += e[1]; maxRooms = Math.max(maxRooms, rooms); }
    return maxRooms;
}

# LC 253 Meeting Rooms II
# NOTE : there're also priority queue, sorting approaches

# V0
# IDEA : SCANNING LINE : Sort all time points and label the start and end points. Move a vertical line from left to right.
class Solution:
     def minMeetingRooms(self, intervals):
            lst = []
            """
            NOTE THIS !!!
            """
            for start, end in intervals:
                lst.append((start, 1))
                lst.append((end, -1))
            # all of below sort work
            #lst.sort()
            lst.sort(key = lambda x : [x[0], x[1]])
            res, curr_rooms = 0, 0
            for t, n in lst:
                curr_rooms += n
                res = max(res, curr_rooms)
            return res

# V0''
# IDEA : SCANNING LINE
# Step 1 : split intervals to points, and label start, end point
# Step 2 : reorder the points
# Step 3 : go through every point, if start : result + 1, if end : result -1, and record the maximum result in every iteration
class Solution:
    def minMeetingRooms(self, intervals):
        if intervals is None or len(intervals) == 0:
            return 0

        tmp = []

        # set up start and end points 
        for inter in intervals:
            tmp.append((inter[0], True))
            tmp.append((inter[1], False))

        # sort 
        tmp = sorted(tmp, key=lambda v: (v[0], v[1]))

        n = 0
        max_num = 0
        for arr in tmp:
            # start point +1 
            if arr[1]:
                n += 1
            # end point -1 
            else:
                n -= 1 # release the meeting room
            max_num = max(n, max_num)
        return max_num

// LC 2406 - Divide Intervals Into Minimum Number of Groups
// IDEA: Sweep line — +1 on start, -1 on end; start before end at same time (inclusive overlap)
// time = O(N log N), space = O(N)
public int minGroups(int[][] intervals) {
    List<int[]> events = new ArrayList<>();
    for (int[] inv : intervals) {
        events.add(new int[]{inv[0], 1});
        events.add(new int[]{inv[1], -1});
    }
    events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]); // start(+1) before end(-1)
    int cur = 0, max = 0;
    for (int[] e : events) { cur += e[1]; max = Math.max(max, cur); }
    return max;
}

// Alt: Sort + Min-PQ (reuse group when earliest end < current start)
// time = O(N log N), space = O(N)
public int minGroups_pq(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> pq = new PriorityQueue<>(); // stores end times
    for (int[] inv : intervals) {
        if (!pq.isEmpty() && pq.peek() < inv[0]) pq.poll(); // reuse group
        pq.add(inv[1]);
    }
    return pq.size(); // active groups = peak overlap
}

// Alt: Difference array (fixed coordinate range)
// time = O(N + M), space = O(M)  where M = max coordinate
public int minGroups_diff(int[][] intervals) {
    int[] diff = new int[1_000_002];
    for (int[] inv : intervals) { diff[inv[0]]++; diff[inv[1] + 1]--; }
    int max = 0, cur = 0;
    for (int d : diff) { cur += d; max = Math.max(max, cur); }
    return max;
}

// LC 731 - My Calendar II
// IDEA: Track booked and overlaps lists; reject if new booking intersects any overlap
// time = O(N^2), space = O(N)
class MyCalendarTwo {
    List<int[]> booked = new ArrayList<>(), overlaps = new ArrayList<>();
    public boolean book(int start, int end) {
        for (int[] ov : overlaps)
            if (start < ov[1] && end > ov[0]) return false; // triple overlap
        for (int[] bk : booked)
            if (start < bk[1] && end > bk[0])
                overlaps.add(new int[]{Math.max(start, bk[0]), Math.min(end, bk[1])});
        booked.add(new int[]{start, end});
        return true;
    }
}

// LC 2021 - Brightest Position on Street
// IDEA: Sweep line — +1 at range start, -1 at range end+1; track max brightness position
// time = O(N log N), space = O(N)
public int brightestPosition(int[][] lights) {
    List<int[]> events = new ArrayList<>();
    for (int[] light : lights) {
        events.add(new int[]{light[0] - light[1], 1});
        events.add(new int[]{light[0] + light[1] + 1, -1});
    }
    events.sort((a, b) -> a[0] - b[0]);
    int brightness = 0, maxBrightness = 0, ans = 0;
    /** NOTE !!! apply EVERY delta at a coordinate before testing the max.
     *  The comparator leaves same-coordinate events unordered, so a +1 that happens to sort
     *  ahead of a -1 at the same x produces a transient brightness no position actually has —
     *  and that phantom peak is what gets returned.
     */
    for (int i = 0; i < events.size(); ) {
        int x = events.get(i)[0];
        while (i < events.size() && events.get(i)[0] == x) {
            brightness += events.get(i)[1];
            i++;
        }
        if (brightness > maxBrightness) { maxBrightness = brightness; ans = x; }
    }
    return ans;
}

# LC 2021. Brightest Position on Street
# V0
# IDEA : Scanning line, LC 253 MEETING ROOM II
class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        # light range array
        light_r = []
        for p,r in lights:
            light_r.append((p-r,'start'))
            light_r.append((p+r+1,'end'))
        light_r.sort(key = lambda x:x[0])
        # focus on the boundary of light range 
        
        bright = collections.defaultdict(int)
        power = 0
        for l in light_r:
            if 'start' in l:
                power += 1
            else:
                power -= 1
            bright[l[0]] = power # NOTE : we update "power" in each iteration
                
        list_bright = list(bright.values())
        list_position = list(bright.keys())
        
        max_bright = max(list_bright)
        max_bright_index = list_bright.index(max_bright)
        
        return list_position[max_bright_index]

# V0'
# IDEA : Scanning line, meeting room
from collections import defaultdict
class Solution(object):
    def brightestPosition(self, lights):
        # edge case
        if not lights:
            return
        _lights = []
        for x in lights:
            """
            NOTE this !!!
             -> 1) scanning line trick
             -> 2) we add 1 to idx for close session (_lights.append([x[0]+x[1]+1, -1]))
            """
            _lights.append([x[0]-x[1], 1])
            _lights.append([x[0]+x[1]+1, -1])
        _lights.sort(key = lambda x : x)
        #print ("_lights = " + str(_lights))
        d = defaultdict(int)
        up = 0
        for a, b in _lights:
            if b == 1:
                up += 1
            else:
                up -= 1
            d[a] = up
        print ("d = " + str(d))
        _max = max(d.values())
        res = [i for i in d if d[i] == _max]
        #print ("res = " + str(res))
        return min (res)

# V1
# IDEA : LC 253 MEETING ROOM II
# https://leetcode.com/problems/brightest-position-on-street/discuss/1494005/Python%3A-Basically-meeting-room-II
# IDEA :
# So, the only difference in this problem in comparison to meeting room II is that we have to convert our input into intervals, which is straightforward and basically suggested to use by the first example. So, here is my code and here is meeting rooms II https://leetcode.com/problems/meeting-rooms-ii/
class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        intervals, heap, res, best = [], [], 0, 0
        for x, y in lights:
            intervals.append([x-y, x+y])
            
        intervals.sort()

        for left, right in intervals:            
            while heap and heap[0] < left: 
                heappop(heap)
            heappush(heap, right)
            if len(heap) > best:
                best = len(heap)
                res = left
        return res

events = [[1,4],[1,1]]     day 1: pq = [1, 4]
                           pop 1 ✅ -> day 2: pq = [4] -> attend        => 2
                           pop 4 ❌ -> day 2: pq = [1] already expired  => 1

# python
# LC 1353. Maximum Number of Events That Can Be Attended
# IDEA: TIME SWEEP + MIN HEAP OF DEADLINES (greedy, earliest-deadline-first)

# V0 : day-jumping  -> time = O(n log n), space = O(n)  (independent of day range)
import heapq

class Solution(object):
    def maxEvents(self, events):
        events.sort()          # by start day
        pq = []                # NOTE !!! min heap of END days
        i = day = ans = 0
        n = len(events)

        while i < n or pq:
            # nothing open -> fast-forward the sweep to the next start day
            if not pq:
                day = events[i][0]

            # PUSH: all events opened by `day`
            while i < n and events[i][0] <= day:
                heapq.heappush(pq, events[i][1])
                i += 1

            # PURGE: lazy-delete expired deadlines
            while pq and pq[0] < day:
                heapq.heappop(pq)

            # ATTEND: earliest deadline, consume this day
            if pq:
                heapq.heappop(pq)
                ans += 1
                day += 1

        return ans


# V0-1 : scan every day  -> time = O(D + n log n), D = day range (1e5), space = O(n)
class Solution(object):
    def maxEvents(self, events):
        events.sort(key=lambda x: -x[0])     # DESC so events.pop() = smallest start
        end_days = []
        ans = 0
        for day in range(1, 100001):
            while events and events[-1][0] <= day:      # PUSH
                heapq.heappush(end_days, events.pop()[1])
            while end_days and end_days[0] < day:       # PURGE
                heapq.heappop(end_days)
            if end_days:                                # ATTEND
                heapq.heappop(end_days)
                ans += 1
        return ans

// LC 1353 - Maximum Number of Events That Can Be Attended
// IDEA: time sweep + min-PQ of end days; each day attend the earliest deadline
// time = O(N log N), space = O(N)
public int maxEvents(int[][] events) {
    Arrays.sort(events, (a, b) -> a[0] - b[0]);          // by start day
    PriorityQueue<Integer> pq = new PriorityQueue<>();   // end days (deadlines)
    int i = 0, day = 0, ans = 0, n = events.length;

    while (i < n || !pq.isEmpty()) {
        if (pq.isEmpty()) day = events[i][0];                        // jump time
        while (i < n && events[i][0] <= day) pq.add(events[i++][1]); // PUSH
        while (!pq.isEmpty() && pq.peek() < day) pq.poll();          // PURGE expired
        if (!pq.isEmpty()) { pq.poll(); ans++; day++; }               // ATTEND
    }
    return ans;
}

START, END = -1, 1        # -1 < 1  ->  plain events.sort() puts START first at ties

firstList = [[0,2],[5,10]]   secondList = [[1,5],[8,12]]

events (sorted, START=-1 first at ties):
  (0,S) (1,S) (2,E) (5,S) (5,E) (8,S) (10,E) (12,E)

x   type   active  action
--------------------------------------------------
0   START  0->1    -
1   START  1->2    overlap OPENS   -> start_pos = 1
2   END    2->1    active==2       -> emit [1, 2]
5   START  1->2    overlap OPENS   -> start_pos = 5   (START before END at x=5 !!)
5   END    2->1    active==2       -> emit [5, 5]     <- single-point intersection
8   START  1->2    overlap OPENS   -> start_pos = 8
10  END    2->1    active==2       -> emit [8, 10]
12  END    1->0    active==1       -> nothing

ans = [[1,2],[5,5],[8,10]]

# python
# LC 986 - Interval List Intersections
# IDEA: SCAN LINE — merge both lists into one event stream, emit stretches where coverage == 2
# time = O((m+n) log(m+n)), space = O(m+n)
class Solution(object):
    def intervalIntersection(self, firstList, secondList):
        # NOTE !!! START = -1 so that a plain sort() puts START BEFORE END at ties
        #          (closed intervals -> touching intervals DO intersect, e.g. [5,5])
        START, END = -1, 1

        events = []
        # 1) intervals -> discrete events (BOTH lists go into the SAME stream)
        for s, e in firstList:
            events.append((s, START))
            events.append((e, END))
        for s, e in secondList:
            events.append((s, START))
            events.append((e, END))

        # 2) sort by coordinate; ties -> START(-1) before END(1)
        events.sort()

        ans = []
        active_count = 0
        start_pos = None

        # 3) sweep the timeline
        for x, event_type in events:
            if event_type == START:
                active_count += 1
                if active_count == 2:        # both lists now cover x -> overlap OPENS
                    start_pos = x
            else:  # END
                if active_count == 2:        # overlap was open -> it CLOSES here
                    ans.append([start_pos, x])
                active_count -= 1

        return ans

// java
// LC 986 - Interval List Intersections
// IDEA: scan line — one merged event stream; emit while coverage == 2
// time = O((m+n) log(m+n)), space = O(m+n)
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    List<int[]> events = new ArrayList<>();
    for (int[] iv : firstList)  { events.add(new int[]{iv[0], -1}); events.add(new int[]{iv[1], 1}); }
    for (int[] iv : secondList) { events.add(new int[]{iv[0], -1}); events.add(new int[]{iv[1], 1}); }

    // ties: -1 (START) before 1 (END)  -> closed intervals, single-point overlaps survive
    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));

    List<int[]> ans = new ArrayList<>();
    int active = 0, startPos = 0;

    for (int[] ev : events) {
        if (ev[1] == -1) {                       // START
            if (++active == 2) startPos = ev[0];
        } else {                                 // END
            if (active == 2) ans.add(new int[]{startPos, ev[0]});
            active--;
        }
    }
    return ans.toArray(new int[ans.size()][2]);
}

# python
# LC 986 - Interval List Intersections (scan line, per-list counters)
# IDEA: track active count PER LIST; intersection is open iff EVERY list has coverage > 0
# time = O((m+n) log(m+n)), space = O(m+n)
class Solution(object):
    def intervalIntersection(self, firstList, secondList):
        events = []
        for s, e in firstList:                 # list_type = 0
            events.append((s, 1, 0))
            events.append((e, -1, 0))
        for s, e in secondList:                # list_type = 1
            events.append((s, 1, 1))
            events.append((e, -1, 1))

        # ties: start(+1) BEFORE end(-1)  ->  -x[1] as secondary key
        events.sort(key=lambda x: (x[0], -x[1]))

        ans = []
        active_first = active_second = 0
        intersection_start = None

        for pos, delta, list_type in events:
            if list_type == 0:
                active_first += delta
            else:
                active_second += delta

            if active_first > 0 and active_second > 0:      # intersection is OPEN
                if intersection_start is None:
                    intersection_start = pos
            else:                                            # it just CLOSED here
                if intersection_start is not None:
                    ans.append([intersection_start, pos])
                    intersection_start = None

        return ans