[백준 - C#] 1931번 회의실 배정

문제링크

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

1931번: 회의실 배정

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.
각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

문제정리

이번 문제는 여러개의 회의 시간이 주어지는데 겹치지 않는 시간으로 가장 많이 회의를 할 수 있는 최대 개수를 구하는 문제입니다.

 

회의의 최대 개수를 구하려면 어떻게 할까 고민하다가, 회의가 일찍 끝나는 순서대로 회의를 정렬하고 카운팅을 하면 되지 않을까 생각이 되어 코드를 작성하였습니다.

 

값을 입력 받고 end(회의 끝나는 시간)를 기준으로 정렬하는데 Array.Sort를 사용하였으며 예제는 아래 이미지와 같습니다.

ex) 정렬

end로 정렬한다고 해도 같은 경우가 있어 회의 시작 순서가 또 빠른경우로 정렬하도록 추가하였습니다.

그다음 회의 종료 시점이 다음 회의 시작지점보다 적다면 endTime을 갱신해주고 카운팅을 추가하여 회의의 개수를 계산하였습니다.

 

 

C# 코드

        static void Main(string[] args)
        {
            StreamWriter writer = new StreamWriter(OpenStandardOutput());
            StreamReader reader = new StreamReader(OpenStandardInput());
 
            int N = int.Parse(reader.ReadLine());
            (int start, int end)[] time = new (int, int)[N];
 
            for (int i = 0; i < N; i++)
            {
                string[] input = reader.ReadLine().Split();
                time[i] = (int.Parse(input[0]), int.Parse(input[1]));
            }
 
            Array.Sort(time, (x, y) => Compare(x, y)); // end를 기준으로 오름차순
 
            int count = 0; // 회의 가능 한 수
            int endTime = 0;
 
            for (int i = 0; i < N; i++)
            {
                if (endTime <= time[i].start) // 회의 종료 시점이 다음 회의 시작지점보다 적다면
                {
                    endTime = time[i].end;
                    count++;
                }
            }
 
            writer.WriteLine(count);
 
            writer.Close();
            reader.Close();
 
            int Compare((int start, int end) x, (int start, int end) y)
            {
                if (x.end == y.end) // 끝나는 순서가 같다면
                    return (x.start < y.start) ? -1 : 1; // 시작하는 순서가 빠른 순으로
                else
                    return (x.end < y.end) ? -1 : 1; // 끝나는 순서가 빠른 순으로
            }
        }

Array.Sort에 대한 참고자료 ( https://constructionsite.tistory.com/24 )

1931 번에 대한 좋은 문제풀이 ( https://kim6394.tistory.com/67 )

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.