[백준] 1931번: 회의실 배정

https://www.acmicpc.net/problem/1931

initial

This is very similar to min. arrows to burst balloons in Leetcode. We want to get the meetings that end the earliest and prioritise them.

To find the largest number of meetings using the given start and end times, you need to sort them in order of the meetings that end the fastest. The reason is simple. The sooner it ends, the more meetings there are to consider later. This is because if you prioritize sorting in order of starting early, it may end later.

To give a simple example:

4

0 10

3 4

2 3

1 2

If you sort them in start order ,( 0 10) one meeting is possible, but if you sort them by end time (1 2) (2 3) (3 4), a total of 3 meetings are possible.

So I thought just sorting by x[1] with lambda will do the trick. But I forgot to think of edge cases. What if the ending time is the same??

If the end time is the same, they should be sorted in order of earliest start.

for example

2

2 2

1 2

In the case of this state, it becomes (2 2), and since the start time of (1 2) is earlier than the end time of (2 2), it is ignored and 1 meeting is reported. However, if (1 2) is selected first through sorting, (2 2) can also be selected since you can simultaneously start at time=2 and end at time=2, so the number of possible meetings is determined as number 2.

Therefore, the sorting must be done in the following order:
1. In ascending order of end time
2. In ascending order of start time .

solution

n= int(input())
lst = [list(map(int,input().split())) for _ in range(n)]
lst.sort(key = lambda x: x[0])
lst.sort(key = lambda x: x[1])
count =0
prev = 0
for i in lst:
    start,end = i
    if start>=prev:
        count+=1
        prev=end
    else:
        continue
print(count)

you can do the sorting in 1 go via a tuple in lambda

lst.sort(key = lambda x: (x[1], x[0]))

revisited jan 23rd

i solved it. but i dont think sorting by 0th and then 1st index is right. Like I said in my explanation it should be that (x[1], x[0]).

complexity

I am assuming time is O(n log n) due to sorting and O(n) space complexity of that list we are storing elements.

yes